Mathematical Construction Methods - Automatic Generation of Combinatorial Test Data - page 20

Fig. 2.4 Construct an

0000
0111
0222
1021
1102
1210
2012
2120
2201

OA ( 9 , 3 4 , 2 ) from

2-MOLS(3)

012 012

201 120

120 201

Suppose that { LS 1 ··· LS k } is a set of k mutually orthogonal Latin squares of order

n , and LS f ( denotes the element in the i th row, j th column of LS f . For each

combination of i and j (0

i , j )

≤ i ≤ n − 1, 0 ≤ j ≤ n − 1), we form a ( k + 2 ) -tuple

. Then we use these tuples as row vectors to form a
matrix. Obviously the resulting matrix is an OA

i , j , LS 1 ( i , j ),..., LS k ( i , j )

n 2 n k + 2

( , , 2 ) .

3 4 Example 2.3 In Fig. 2.4 , the matrix on the right is an OA constructed from

the 2-MOLS(3) on the left. The first column represents the row indices of 2-MOLS(3);
the second column represents the column indices of 2-MOLS(3); the third column
contains the elements in the first latin square, and the last column contains the ele-
ments in the second latin square.

( 9 , , 2 )

2.2 Mathematical Methods for Constructing Covering Arrays

A covering array is optimal if it has the smallest possible number N of rows. As
mentioned in Chap. 1 , this smallest number is called the covering array number
(CAN). Formally, CAN

.CAN
is a vital attribute of covering arrays. It serves as the lower bound of the size of the
test suite. CAN can always be obtained as the by-product of the construction of CAs.

( d 1 · d 2 ··· d k , t ) = min { N |∃ CA ( N , d 1 · d 2 ··· d k , t ) }

2.2.1 Simple Constructions

2.2.1.1 Column-Collapsing

Given a CA ( N , d 1 ··· d i ··· d k , t ) , if we delete an arbitrary column i , we will get a

CA ( N , d 1 ··· d i − 1 · d i + 1 ··· d k , t ) .So

CAN ( d 1 ··· d i − 1 · d i + 1 ··· d k , t ) ≤ CAN ( d 1 ··· d i ··· d k , t ).