Ticket #16391: is_incomplete_orthogonal_array.py

File is_incomplete_orthogonal_array.py, 3.5 KB (added by vdelecroix, 5 years ago)

an implementation of is_incomplete_orthogonal_array

Line
1r"""
2An incomplete orthogonal array IOA(k,n; h1, ..., hs) is a quadruple:
3- V a set of size n
4- H1, H2, ..., Hs disjoint subsets of V of size b1, ..., bs
5- B a set of subsets of size k
6such that for every pair of columns, the set of rows is the set of possible
7pairs except when the belong to the same hole.
8
9As a consequence the number of blocks is n^2 - \sum_{i=1}^s hi^2
10
11If there exists an IOA(k,n; h1, ..., hs) and OA(k,hi) for i=1,...,s there
12trivially exists a OA(k,n).
13
14Our implementation is such that
15- V is {0, ..., n-1}
16- the holes are at the end, namely Hs = {n-1, ..., n-h1}, etc
17"""
18
19#TODO: add it to the database
20def IMOLS_6_2_2():
21    r"""
22    An incomplete set of MOLS (6,2) with a hole of size 2.
23
24    EXAMPLES::
25
26        sage: IOA = IOA_FROM_IMOLS(IMOLS_6_2_2(), 2, 6)
27        sage: IOA
28        [[0, 0, 4, 0], [0, 1, 5, 1], [0, 2, 2, 4], [0, 3, 3, 5],
29        ...
30         [5, 0, 2, 2], [5, 1, 1, 0], [5, 2, 3, 1], [5, 3, 0, 3]]
31        sage: is_incomplete_orthogonal_array(IOA, 4, 6, (2,))
32        True
33    """
34    M = [
35    matrix(6,[
36      4,5,2,3,0,1,
37      1,0,5,4,2,3,
38      5,4,0,1,3,2,
39      3,2,4,5,1,0,
40      0,3,1,2,-1,-1,
41      2,1,3,0,-1,-1]),
42    matrix(6,[
43      0,1,4,5,2,3,
44      5,4,0,1,3,2,
45      3,2,5,4,0,1,
46      4,5,3,2,1,0,
47      1,3,2,0,-1,-1,
48      2,0,1,3,-1,-1])]
49
50    return M
51
52def IOA_from_IMOLS(IMOLS, k, n):
53    IOA = []
54    for i in xrange(n):
55        for j in xrange(n):
56            if IMOLS[i,j] != -1:
57                IOA.append([i,j] + [IMOLS[kk][i,j] for kk in xrange(k)])
58    return IOA
59
60def is_incomplete_orthogonal_array(IOA, k, n, holes, verbose=False):
61    r"""
62    Check whether IOA is an incomplete orthogonal array with the given holes.
63
64    We assume that the set V is {0, ..., n-1} and the holes are the higher
65    indices. Namely H1 = {n-1, n-2, ..., n-h1}, H2 = {n-h1-1,..., n-h1-h2}`,
66    ...
67
68    EXAMPLES::
69
70        sage: OA = [
71        ....:  [0,1,2], [0,2,1], [1,0,2],
72        ....:  [1,2,0], [2,0,1], [2,1,0],
73        ....:  [0,0,0], [1,1,1], [2,2,2]]
74        sage: is_incomplete_orthogonal_array(OA, 3, 3, ())
75        True
76        sage: OA.pop(-1)
77        [2, 2, 2]
78        sage: is_incomplete_orthogonal_array(OA, 3, 3, (1,))
79        True
80        sage: OA.pop(-1)
81        [1, 1, 1]
82        sage: is_incomplete_orthogonal_array(OA, 3, 3, (1, 1))
83        True
84        sage: OA.pop(-1)
85        [0, 0, 0]
86        sage: is_incomplete_orthogonal_array(OA, 3, 3, (1, 1, 1))
87        True
88    """
89    if any(len(block) != k for block in IOA):
90        if verbose:
91            print("some block does not has length %d"%k)
92        return False
93
94    b = n**2 - sum(h**2 for h in holes)
95    if len(IOA) != b:
96        if verbose:
97            print("there must be n^2 - sum h_i^2 = %d blocks"%holes)
98        return False
99
100    m = n - sum(holes)
101    VV = [range(m)]
102    for h in holes:
103        VV.append(range(m,m+h))
104        m += h
105
106    m = n - sum(holes)
107    ref = [(v1,v2) for v1 in xrange(m) for v2 in xrange(m)]
108    for i in xrange(len(VV)):
109        for j in xrange(i+1,len(VV)):
110            for v1 in VV[i]:
111                for v2 in VV[j]:
112                    ref.append((v1,v2))
113                    ref.append((v2,v1))
114
115    ref = sorted(ref)
116    assert len(ref) == b
117
118    for i in xrange(k):
119        for j in xrange(i+1,k):
120            s = sorted((block[i],block[j]) for block in IOA)
121            if s != ref:
122                if verbose:
123                    print("columns %d and %d are wrong"%(i,j))
124                return False
125
126    return True
127
128
129