# How to derive the number of pairwise combinations of a set of factors?

I am trying to understand pairwise testing.

How many combinations of tests would be there for example, if

a can take values from 1 to m

b can take values from 1 to n

c can take values from 1 to p

a, b and c can take m, n and p distinct values respectively. What are the total number of pairwise combinations possible?

With a pairwise testing tool that I am testing, I am getting 40 results for m = n = p = 6. I am trying to mathematically understand how I get 40 values.

-
Not sure what you are asking. Maybe an example to make it clearer? – Aryabhata Sep 8 '10 at 18:45
@Moron: updated. – Lazer Sep 8 '10 at 18:57

Pairwise testing tests for all possible 2-way interactions efficiently -- I gave a quick overview here: http://cstheory.stackexchange.com/questions/891/

You are looking for strength 2 covering arrays. In each pair of columns every pair of symbols occur -- this ensures all 2-way interactions are observed in some way. Here's a very simple example of a covering array of strength 2 with 2 columns:

11
12
21
22
12


What castel has drawn is essentially the Latin square:

123456
612345
561234
456123
345612
234561


If you look at each entry and write the list (r,c,s), where r is the row index, c is the column index, and s is the symbol, you will construct an orthogonal array (as depicted below) -- a covering array of strength 2 with the minimum number of rows (36).

111
122
133
...
661


In fact, Latin squares exist for all orders n. So if you have three columns (e.g. three variables) and n symbols for each variable, then you can always find a strength 2 covering array with n2 rows.

Many combinatorial designs give rise to particularly efficient covering arrays. Strength 2 covering arrays with more than three columns and n2 rows are equivalent to sets of mutually orthogonal Latin squares (the reference shows the construction).

In your case, if you have 40 results, then you are not using the most efficient covering array.

-

After reading this page, it seems that pairwise testing requires a set of test cases in which every pair of values from any two of the n categories occurs at least once among the test case n-tuples. In the present case, the problem is to find a minimal subset of the 6x6x6 = 216 total triples (a,b,c) such that

• each pair of values for a and b
occurs at least once, i.e. (a,b,*),

• each pair of a and c values occurs
at least once, i.e. (a,*,c)

• each pair of b and c values occurs at least once, i.e. (*,b,c)

Any subset satisfying these requirements must have at least 36 elements just to satisfy the (a,b,*) requirement. In the present case I think 36 test cases are also sufficient, as in the following set of triples:

(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6)

(2, 1, 6), (2, 2, 1), (2, 3, 2), (2, 4, 3), (2, 5, 4), (2, 6, 5)

(3, 1, 5), (3, 2, 6), (3, 3, 1), (3, 4, 2), (3, 5, 3), (3, 6, 4)

(4, 1, 4), (4, 2, 5), (4, 3, 6), (4, 4, 1), (4, 5, 2), (4, 6, 3)

(5, 1, 3), (5, 2, 4), (5, 3, 5), (5, 4, 6), (5, 5, 1), (5, 6, 2)

(6, 1, 2), (6, 2, 3), (6, 3, 4), (6, 4, 5), (6, 5, 6), (6, 6, 1)

In this example each of the three kinds of pairs occurs once and only once, i.e. there is no overlap. I don't think this will be possible in general, so it might not always be easy to come up with minimal subsets that cover all the cases.

-
This works for m=n=p, just take c = (a+b) mod m. (Or any other multiplication table of a group with m elements :). – yatima2975 Sep 9 '10 at 15:47

If each parameter had $10$ choices you'd be testing $300$ vs $1000$ combinations, namely hold $\rm a$ constant and vary $\rm b,c$ through $10\cdot 10 = 100$ values. Similarly hold, $\rm b$ constant; then $\rm c$. As the number of variables $\rm k$ increases you get better savings, roughly $\rm (k N)^2$ vs. $\rm N^k$, where $\rm N =$ max domain size. For QA purposes usually such rough upper bounds suffice. Do you have an intended application where you need something more precise? If so perhaps you should reveal some further details, e.g. the distribution of the sizes of the domains, etc.

EDIT: After reviewing your latest revision, it appears that the following web pages may be of interest: Pairwise Testing, which refers to various Taguchi methods such as those here. See also these links to introductions to combinatorial testing.

-