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?