# Ticket #16391: is_incomplete_orthogonal_array.py

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

Line | |
---|---|

1 | r""" |

2 | An 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` |

6 | such that for every pair of columns, the set of rows is the set of possible |

7 | pairs except when the belong to the same hole. |

8 | |

9 | As a consequence the number of blocks is `n^2 - \sum_{i=1}^s hi^2` |

10 | |

11 | If there exists an `IOA(k,n; h1, ..., hs)` and `OA(k,hi)` for `i=1,...,s` there |

12 | trivially exists a `OA(k,n)`. |

13 | |

14 | Our 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 |

20 | def 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 | |

52 | def IOA_from_IMOLS(IMOLS, k, n): |

53 | IOA = [] |

54 | for i in xrange(n): |

55 | for j in xrange(n): |

56 | if IMOLS[0][i,j] != -1: |

57 | IOA.append([i,j] + [IMOLS[kk][i,j] for kk in xrange(k)]) |

58 | return IOA |

59 | |

60 | def 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 |