Cython functions for combinatorial designs
This module implements the design methods that need to be somewhat efficient.
Test if is a
-difference matrix.
A matrix is a
-difference matrix if its entries are
element of
, and if for any two rows
of
and
there
are exactly
values
such that
.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.designs_pyx import is_difference_matrix
sage: q = 3**3
sage: F = GF(q,'x')
sage: M = [[x*y for y in F] for x in F]
sage: is_difference_matrix(M,F,q,verbose=1)
True
sage: B = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
....: [0, 1, 2, 3, 4, 2, 3, 4, 0, 1],
....: [0, 2, 4, 1, 3, 3, 0, 2, 4, 1]]
sage: G = GF(5)
sage: B = [[G(b) for b in R] for R in B]
sage: is_difference_matrix(zip(*B),G,3,2)
True
Bad input:
sage: for R in M: R.append(None)
sage: is_difference_matrix(M,F,q,verbose=1)
The matrix has 28 columns but k=27
False
sage: for R in M: _=R.pop(-1)
sage: M.append([None]*3**3)
sage: is_difference_matrix(M,F,q,verbose=1)
The matrix has 28 rows instead of lambda(|G|-1+2u)+mu=1(27-1+2.0)+1=27
False
sage: _= M.pop(-1)
sage: for R in M: R[-1] = 0
sage: is_difference_matrix(M,F,q,verbose=1)
Columns 0 and 26 generate 0 exactly 27 times instead of the expected mu(=1)
False
sage: for R in M: R[-1] = 1
sage: M[-1][-1] = 0
sage: is_difference_matrix(M,F,q,verbose=1)
Columns 0 and 26 do not generate all elements of G exactly lambda(=1) times. The element x appeared 0 times as a difference.
False
Checks that input is a Group Divisible Design on
For more information on Group Divisible Designs, see GroupDivisibleDesign.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.designs_pyx import is_group_divisible_design
sage: TD = designs.transversal_design(4,10)
sage: groups = [range(i*10,(i+1)*10) for i in range(4)]
sage: is_group_divisible_design(groups,TD,40,lambd=1)
True
TESTS:
sage: TD = designs.transversal_design(4,10)
sage: groups = [range(i*10,(i+1)*10) for i in range(4)]
sage: is_group_divisible_design(groups,TD,40,lambd=2,verbose=True)
the pair (0,10) has been seen 1 times but lambda=2
False
sage: is_group_divisible_design([[1,2],[3,4]],[[1,2]],40,lambd=1,verbose=True)
groups is not a partition of [0,...,39]
False
sage: is_group_divisible_design([range(40)],[[1,2]],40,lambd=1,verbose=True)
the pair (1,2) belongs to a group but appears in some block
False
sage: is_group_divisible_design([range(40)],[[2,2]],40,lambd=1,verbose=True)
The following block has repeated elements: [2, 2]
False
sage: is_group_divisible_design([range(40)],[["e",2]],40,lambd=1,verbose=True)
e does not belong to [0,...,39]
False
sage: is_group_divisible_design([range(40)],[["e",2]],40,G=[5],lambd=1,verbose=True)
a group has size 40 while G=[5]
False
sage: is_group_divisible_design([range(40)],[["e",2]],40,K=[1],lambd=1,verbose=True)
a block has size 2 while K=[1]
False
Check that the integer matrix is an
.
See orthogonal_array() for a definition.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.designs_pyx import is_orthogonal_array
sage: OA = designs.orthogonal_arrays.build(8,9)
sage: is_orthogonal_array(OA,8,9)
True
sage: is_orthogonal_array(OA,8,10)
False
sage: OA[4][3] = 1
sage: is_orthogonal_array(OA,8,9)
False
sage: is_orthogonal_array(OA,8,9,verbose=True)
Columns 0 and 3 are not orthogonal
False
sage: is_orthogonal_array(OA,8,9,verbose=True,terminology="MOLS")
Squares 0 and 3 are not orthogonal
False
TESTS:
sage: is_orthogonal_array(OA,8,9,t=3)
Traceback (most recent call last):
...
NotImplementedError: only implemented for t=2
sage: is_orthogonal_array([[3]*8],8,9,verbose=True)
The number of rows is 1 instead of 9^2=81
False
sage: is_orthogonal_array([[3]*8],8,9,verbose=True,terminology="MOLS")
All squares do not have dimension n^2=9^2
False
sage: is_orthogonal_array([[3]*7],8,9,verbose=True)
Some row does not have length 8
False
sage: is_orthogonal_array([[3]*7],8,9,verbose=True,terminology="MOLS")
The number of squares is not 6
False
Up to relabelling, there is a unique . So their number is just the
cardinality of the relabeling group which is
and has
cardinality
:
sage: from itertools import product
sage: n = 0
sage: for a in product(product((0,1), repeat=3), repeat=4):
....: if is_orthogonal_array(a,3,2):
....: n += 1
sage: n
48
Checks that input is a Pairwise Balanced Design (PBD) on
For more information on Pairwise Balanced Designs (PBD), see PairwiseBalancedDesign.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.designs_pyx import is_pairwise_balanced_design
sage: sts = designs.steiner_triple_system(9)
sage: is_pairwise_balanced_design(sts,9,[3],1)
True
sage: TD = designs.transversal_design(4,10).blocks()
sage: groups = [range(i*10,(i+1)*10) for i in range(4)]
sage: is_pairwise_balanced_design(TD+groups,40,[4,10],1,verbose=True)
True
TESTS:
sage: from sage.combinat.designs.designs_pyx import is_pairwise_balanced_design
sage: is_pairwise_balanced_design(TD+groups,40,[4,10],2,verbose=True)
the pair (0,1) has been seen 1 times but lambda=2
False
sage: is_pairwise_balanced_design(TD+groups,40,[10],1,verbose=True)
a block has size 4 while K=[10]
False
sage: is_pairwise_balanced_design([[2,2]],40,[2],1,verbose=True)
The following block has repeated elements: [2, 2]
False
sage: is_pairwise_balanced_design([["e",2]],40,[2],1,verbose=True)
e does not belong to [0,...,39]
False
Test if the matrix is a -quasi-difference matrix
Let be an abelian group of order
. A
-quasi-difference matrix (QDM) is a matrix
with
rows and
columns, with each entry either
equal to None (i.e. the ‘missing entries’) or to an element of
. Each
column contains exactly
empty entries, and each row contains at
most one None. Furthermore, for each
, the multiset
contains times every nonzero element of
and contains
times
.
INPUT:
EXAMPLES:
Differences matrices:
sage: from sage.combinat.designs.designs_pyx import is_quasi_difference_matrix
sage: q = 3**3
sage: F = GF(q,'x')
sage: M = [[x*y for y in F] for x in F]
sage: is_quasi_difference_matrix(M,F,q,1,1,0,verbose=1)
True
sage: B = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
....: [0, 1, 2, 3, 4, 2, 3, 4, 0, 1],
....: [0, 2, 4, 1, 3, 3, 0, 2, 4, 1]]
sage: G = GF(5)
sage: B = [[G(b) for b in R] for R in B]
sage: is_quasi_difference_matrix(zip(*B),G,3,2,2,0)
True
A quasi-difference matrix from the database:
sage: from sage.combinat.designs.database import QDM
sage: G,M = QDM[38,1][37,1,1,1][1]()
sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=1,u=1)
True
Bad input:
sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=1,u=3,verbose=1)
The matrix has 39 rows instead of lambda(|G|-1+2u)+mu=1(37-1+2.3)+1=43
False
sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=2,u=1,verbose=1)
The matrix has 39 rows instead of lambda(|G|-1+2u)+mu=1(37-1+2.1)+2=40
False
sage: M[3][1] = None
sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=1,u=1,verbose=1)
Row 3 contains more than one empty entry
False
sage: M[3][1] = 1
sage: M[6][1] = None
sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=1,u=1,verbose=1)
Column 1 contains 2 empty entries instead of the expected lambda.u=1.1=1
False