<p>Great question! This comes up in survey design, where you want a few different versions of the survey that each only contain a subset of the questions, but you want every pair (or t-tuple) of questions to have been asked at least once.</p>

<p>This is called <strong>covering design</strong>, and is a variant of the classic <em>set cover problem</em>. As you can read in an excellent <a href="https://math.stackexchange.com/q/1734855/127715">Mathematics Stack Exchange post</a> on the topic, folks use notation C(v, k, t) indicating the minimum number of k-element subsets you need to draw (k=3 in your case) from a v-element set (v=5 in your case) such that every t-element subset in the entire set (t=2 in your case) is contained within one of your selected subsets. Folks have evaluated this function for many different (v, k, t) tuples; see, for instance, <a href="https://ljcr.dmgordon.org/cover/table.html" rel="nofollow noreferrer">https://ljcr.dmgordon.org/cover/table.html</a> . We can read from that table that C(5, 3, 2) = 4, with the following as one possible design:</p>

<pre><code>  1  2  3
  1  4  5
  2  3  4
  2  3  5
</code></pre>

<p>First and foremost, this problem is NP-hard, so all known exact algorithms will scale exponentially in inputs v, k, and t. So while you may be able to solve small instances exactly by enumeration or some more clever exact method (e.g. integer programming), you will likely need to resort to heuristic methods as the problem size gets very large.</p>

<p>One possibility in this direction is lexicographic covering, as proposed in <a href="https://arxiv.org/pdf/math/9502238.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/math/9502238.pdf</a> (you will note that many of the solutions on the site linked above list "lex covering" as the method of construction). Basically you list out all possible k-tuples in lexicographic order:</p>

<pre><code>123
124
125
134
135
145
234
235
245
345
</code></pre>

<p>Then you greedily add the k-tuple that covers the most previously uncovered t-tuples, breaking ties using the lexicographic ordering.</p>

<p>Here's how the algorithm works in our case:</p>

<ol>
<li><p>At the beginning every 3-tuple covers 3 different 2-tuples, so we add <code>123</code> since it is lexicographically earliest.</p></li>
<li><p>After doing this, the 2-tuples of <code>12</code>, <code>13</code>, and <code>23</code> have been covered, while all remaining 2-tuples are not covered. A number of 3-tuples cover 3 more 2-tuples, e.g. <code>145</code> and <code>245</code>. We pick <code>145</code>, since it is lexicographically first, covering <code>14</code>, <code>45</code>, and <code>15</code>.</p></li>
<li><p>Now we have 4 remaining uncovered 2-tuples -- <code>24</code>, <code>25</code>, <code>34</code>, and <code>35</code>. No 3-tuple covers 3 of these, but several cover 2, e.g. <code>234</code> and <code>345</code>. We select <code>234</code> as the lexicographically earliest.</p></li>
<li><p>We have two remaining uncovered 2-tuples -- <code>25</code> and <code>35</code>. We select <code>235</code> as the only 3-tuple that covers both.</p></li>
</ol>

<p>We end up with the exact solution shown above. Importantly, this is just a heuristic method -- it doesn't give any guarantee that 4 is the smallest number of 3-tuples needed to cover all pairs in a set with 5 elements. In this case, a lower bound by Schönheim (a reference is provided in the linked article above) convinces us that, in fact, C(5, 3, 2) cannot be smaller than 4. We conclude that the solution from lexicographic covering is in fact optimal.</p>

<p>You would need a tweak to cover each t-tuple a certain number of times r. One obvious one would just be to repeat each tuple to be covered "r" times, and then run lex covering as usual (so for instance in the first step above each 3-tuple would cover 9 2-tuples with r=3). Of course this remains a heuristic for your overall problem due to the use of lex covering.</p>
Efficiently picking combinations of Integers
<p>Let's say we have a 5x5 matrix, filled with 0s.</p>

<pre><code>myMatrix &lt;- matrix(rep(0, 25), ncol = 5)
</code></pre>

<p>Now, let's pick a triplet of integers between 1 and 5.</p>

<pre><code>triplet &lt;- c(1,2,3)
</code></pre>

<p>For all combinations of this triplet we now add 1 in the matrix,
with this function:</p>

<pre><code>addCombinationsToMatrix &lt;- function(.matrix, .triplet){
    indexesToChange &lt;- as.matrix(expand.grid(.triplet, .triplet))
    .matrix[indexesToChange] &lt;- .matrix[indexesToChange] + 1
    .matrix
}
</code></pre>

<p>Using the function, we go from</p>

<pre><code>myMatrix

     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    0    0    0
[2,]    0    0    0    0    0
[3,]    0    0    0    0    0
[4,]    0    0    0    0    0
[5,]    0    0    0    0    0
</code></pre>

<p>to</p>

<pre><code>myMatrix &lt;- addCombinationsToMatrix(myMatrix, triplet)
myMatrix

     [,1] [,2] [,3] [,4] [,5]
[1,]    1    1    1    0    0
[2,]    1    1    1    0    0
[3,]    1    1    1    0    0
[4,]    0    0    0    0    0
[5,]    0    0    0    0    0
</code></pre>

<p>If we pick another triplet we move on to</p>

<pre><code>nextTriplet &lt;- 2:4
myMatrix &lt;- addCombinationsToMatrix(myMatrix, nextTriplet)
myMatrix

     [,1] [,2] [,3] [,4] [,5]
[1,]    1    1    1    0    0
[2,]    1    2    2    1    0
[3,]    1    2    2    1    0
[4,]    0    1    1    1    0
[5,]    0    0    0    0    0
</code></pre>

<p>So, row-column combinations represent how often two integers have been shown
together in a triplet: 3 and 4 have been shown together once, 2 and 3 have
been shown together twice.</p>

<p><strong>Question</strong>: How can one pick triplets, such that
every combination (1-2, 1-3, 1-4...) was picked at least once
and the number of triplets is minimized.</p>

<p>I'm looking for an algorithm here that picks the next triplet.</p>

<p>Ideally it can be extended to</p>

<ul>
<li>arbitrarily big matrices (10x10, 100x100 ...)</li>
<li>arbitrarily big vectors (quadruplets, quintuplets, n-tuplets)</li>
<li>an arbitrary number of times a combination must have been picked at least</li>
</ul>

<p>Example:</p>

<pre><code>myMatrix
myMatrix &lt;- addCombinationsToMatrix(myMatrix, 1:3)
myMatrix
myMatrix &lt;- addCombinationsToMatrix(myMatrix, 3:5)
myMatrix
myMatrix &lt;- addCombinationsToMatrix(myMatrix, c(1,4,5))
myMatrix
myMatrix &lt;- addCombinationsToMatrix(myMatrix, c(2,4,5))
myMatrix
</code></pre>

<hr>

<p><strong>EDIT</strong>:
Just to be sure: the answer doesn't have to be <code>R</code> code. It can be some other language as well or even pseudo code.</p>

<p><strong>EDIT 2</strong>:
It occured to me now, that there are different ways of measuring efficiency. I actually meant, the algorithm should take as little iterations as possible. The algorithm being fast is also very cool, but not the main goal here.</p>