Backtracking Search - Automatic Generation of Combinatorial Test Data - page 73

0000
0001
0110
0111
1010
1011
1100
1101

0010
0000
0111
0101
1011
1001
1110
1100

1.Swap column 3 with column 4;
2.Permute symbol '0' and '1' in column 3

Fig. 6.10 Two isomorphic instances of OA ( 8 , 2 4 , 2 )

To eliminate row & column symmetries, lexicographic order is imposed along
both rows and columns in an OA. Note that for an OA with mixed factor levels,
column lexicographic order is only imposed on the columns with the same levels. To
break symbol symmetries, the LNH strategy can be applied to each column outside
the init-block.

2 4

Example 6.7 Figure 6.11 demonstrates three solutions of OA . A and B

are lexicographically ordered along both the rows and the columns. Matrix C does
not satisfy the lexicographic order since the third column

( 12 , 3 · , 2 )

≤ lex the fourth column,

thus C would not be encountered in the search process.

Although being quite effective, lexicographic order and LNH are far from enough
to eliminate all symmetries in OAs. There is a class of symmetries arising from the
automorphisms of init-block. If we permute the symbols in the init-block, reconstruct
the init-block by swapping rows, we can always get another OA by performing some
other isomorphic operations outside the init-block. The newly obtained array has
the same init-block, satisfies all constraints of lexicographic order and LNH, hence
would also be encountered during the search. This transformation procedure is called
init-block reconstruction .
We say two OAs are symmetric with respect to (w.r.t.) an init-block reconstruction
if one can be obtained from the other through this reconstruction.

Fig. 6.11 Three Instances of
OA

(a) (b) (c)

00000
00111
01011
01100
10001
10010
11100
11111
20101
20110
21001
21 010

00000
00011
01101
01110
10001
10110
11010
11101
20100
20111
21000
21 011

00000
00101
01010
01111
10011
10110
11000
11101
20011
20100
21001
21 110

2 4

( 12 , 3 · , 2 )