Traverse all permutations of pairs, triples, etc. in a minimal number of batches? I have a collection of test cases $t_1, \ldots, t_n$ for my software. I suspect my tests themselves have a bug, in which some of them share global state and fail if run in the right order.
I would like to find this by running all tests in some order. If the run fails, I'll employ a minimization technique to find a smallest example. Otherwise, my plan is to run the test suite in a different order until I find a failure or give up.
I would like to choose the order in which I run my tests intelligently. For example, if on the second run I run the test cases in the reverse order of the first, the following holds: for every pair of test cases $t_i$ and $t_j$, I have performed one run in which $t_i$ came before $t_j$ and one run in which $t_j$ came before $t_i$.
I would like to achieve something similar for triples of test cases, in $3! = 6$ runs. However, my own exhaustive search suggests that for $n \geq 5$ this is impossible.
What is the smallest number $k$ such that there exists $k$ permutations of $\{1, \ldots, n\}$ containing all triples in all orders between them? Is there a simple scheme for generating such permutations? Is there a scheme which tries all $m$-tuples, for each $m$?
For $n = 4$ the set of permutations $(0, 1, 2, 3), (0, 3, 2, 1), (1, 3, 0, 2), (2, 1, 0, 3), (2, 3, 0, 1), (3, 1, 2, 0)$ tries all triples. One notes that $(0, 1, 2, 3)$ is here but $(3, 2, 1, 0)$ isn't. Is it ever possible to be optimal with respect to both pairs and triples? (i.e. try all orderings of pairs with the first two permutations and all triple-orderings with the first however-many-it-takes permutations)? Is it possible to be optimal with respect to all tuple sizes simultaneously?
 A: I will answer a similar question which I believe may solve your problem, but it will not be a direct answer to the question for $k$. Instead of running $k$ permutations of the tests, you may be satisfied with generating a single sequence (longer than $n$, repeating some tests) containing every possible permutation of length $3$ as a subsequence. A general problem is known as Shortest Common Supersequence Problem (SCS for short), which given a set of strings $S = \{s_1, \dots, s_m\}$ (in your case the strings are permutations of length 3) asks for the shortest string $X$ containing each $s_i$ as a subsequence.
While it was shown that for an arbitrary set $S$ the problem is NP-hard, there exists quite an old research of Newey which may be found here which covers exactly the topic of finding SCS when $S$ is a set of all permutations of some alphabet $A$ of given length $m$. You may be especially interested in statement 2.10:
$$M'(n, 3) = 3n-2$$
saying that the length of SCS containing every 3-permutation of $n$ elements is equal to $3n-2$. That means that there exists a sequence $X$ having length $3n-2$ of the tests such that for every triple of tests each of their permutations will be a subsequence of this SCS. What is even better, Newey gives an algorithm to generate such a sequence in section 8. I will rewrite this code in R (the indices in R start from $1$ instead of $0$, so beware)
A <- 1:7 #There are seven tests in that case
SCS <- c()
n <- length(A)
m <- 3
B <- A[(n-m+2):n]
SCS <- c(SCS, A)
for(i in 1:(m-2)){
  SCS <- c(SCS, A[1:(n-m+1)])
  SCS <- c(SCS, B[1:(m-2)])
  B <- c(B[m-1], B[1:(m-2)])
}
SCS <- c(SCS, A[1:(n-m+1)])
SCS <- c(SCS, B[1])
SCS

Using SCS you naturally satisfy that every $2$-permutation is covered as well, which would not be obvious if you used $k$ permutations. Moreover, the above code works for any $m$ and guarantees that every $i$-tuple of elements for $i \in \{1, \dots, m\}$ is a subsequence of the SCS having length $mn-3m+4$.
A: There is an obvious greedy approximation algorithm which might do something useful, run each test case at most once every run and only  be moderately slow for modest input sizes ;-)
TL;DR: to compute the next run, repeatedly commit to running a $k$-tuple you haven't run yet (in ascending order of $k$), provided this commitment is compatible with the commitments you have made so far. Stop once the next run is uniquely determined (and reset your set of commitments).
The pedantic version:
The algorithm stores every ordering of test cases it has run. To compute the next run when wanting to cover $k$-tuples, count how many times each $k$-tuple has been run in the past (in $O(runs * n^k)$ time).
Go through the $n!/k!$ tuples in ascending order of past run-count; if the current tuple is compatible with the tuples selected so far, select it too. Compatibility between (e.g. $k = 3$) tuples $(a, b, c)$ and $(d, e, f)$ means there exists some ordering of all tests such that $a < b < c$ and $d < e < f$ where $<$ means "is run before".
To test for compatibility, draw up a graph with test cases as vertices. When selecting a tuple, e.g. $(a, b, c)$, add edges $(a, b)$ and $(b, c)$ to this graph (or in general $k - 1$ edges between adjacent elements). Compatibility with a new tuple means the graph is (still) acyclic if that tuple is selected.
The next run is a topological ordering of this graph of constraints, once this ordering is unique (i.e. its transitive closure contains $n(n-1)/2$ edges).
It will become unique (if $k > 1$): assume otherwise, e.g. that there is some pair $\{v, w\}$ with no edges between them in the transitive closure of the constraint graph. For every such constraint graph there is some $k$-tuple containing $v$, $w$ and some other test cases in an ordering compatible with the constraint graph. Since the algorithm failed to stop before iterating through all $k$-tuples, it must have iterated through the tuple with $v$ and $w$ that was compatible with the constraint graph. But then an edge between $v$ and $w$ must have been added to (the transitive closure of) the constraint graph.
I'm spitballing that you can break past-run-count ties any way you like. I'm partial to selecting a random tiebreaker ordering up front and reusing it. (This random tiebreaker also guarantees a unique solution for $k = 1$: the random tiebreaker order.)
Note that selecting a random first run and its reverse as the second run exactly follows this greedy algorithm, first for 1-tuples and then for 2-tuples.
Instead of tracking past run-counts and sorting by it, one might track a "constraint wish list" containing all $k$-tuples in ascending order of $k$. Remove each tuple from this list when you issue a run containing that tuple.  Every $n$-tuple (if compatible with the constraints selected so far) enforces a unique constraint graph so you eventually terminate with a unique next run, until you've tried all $n!$ permutations. At that point, stop and declare "no order dependence found".
