This strategy can be more efficient than one based on exhaustively testing all combinations since many test failures result from the interaction of a relatively small number of factors: often just two of them.

Computing orthogonal arrays for pairwise joins for large domains can be very expensive computationally. Therefore most practical algorithms use approximations.

The algorithm used here makes a list of all pairs that must be covered. Then it constructs combinations greedily by trying to include as many uncovered pairs in each one as possible, preferring pairs used less often over other ones. The combinations produced may not be optimal but empirically it covers all pairs using a sufficiently small number of cases for most practical purposes.

Many thanks to James Bach at Satisfice (www.satisfice.com) for his AllPairs program from which the algorithm used here was adapted.

The choice of considering only 2 factors was made for the sake of implementation convenience. It turns out that an N-wise combination strategy is much more complex to implement efficiently because the general problem is NP-Complete. However, if you should choose to implement such a join strategy on your own, please consider contributing it back to the Gallio project for others to use. Thanks!

See also: .