Cython functions for combinatorial designs¶
This module implements the design methods that need to be somewhat efficient.
Functions¶
-
sage.combinat.designs.designs_pyx.
is_difference_matrix
(M, G, k, lmbda=1, verbose=False)¶ Test if \(M\) is a \((G,k,\lambda)\)-difference matrix.
A matrix \(M\) is a \((G,k,\lambda)\)-difference matrix if its entries are element of \(G\), and if for any two rows \(R,R'\) of \(M\) and \(x\in G\) there are exactly \(\lambda\) values \(i\) such that \(R_i-R'_i=x\).
INPUT:
M
– a matrix with entries fromG
G
– a groupk
– integerlmbda
(integer) – set to \(1\) by default.verbose
(boolean) – whether to print some information when the answer isFalse
.
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(list(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
-
sage.combinat.designs.designs_pyx.
is_group_divisible_design
(groups, blocks, v, G=None, K=None, lambd=1, verbose=False)¶ Checks that input is a Group Divisible Design on \(\{0,...,v-1\}\)
For more information on Group Divisible Designs, see
GroupDivisibleDesign
.INPUT:
groups
– a partition of \(X\). If set toNone
the groups are guessed automatically, and the function returns(True, guessed_groups)
instead ofTrue
blocks
– collection of blocksv
(integers) – size of the ground set assumed to be \(X=\{0,...,v-1\}\).G
– list of integers of which the sizes of the groups must be elements. Set toNone
(automatic guess) by default.K
– list of integers of which the sizes of the blocks must be elements. Set toNone
(automatic guess) by default.lambd
– value of \(\lambda\). Set to \(1\) by default.verbose
(boolean) – whether to display some information when the design is not a GDD.
EXAMPLES:
sage: from sage.combinat.designs.designs_pyx import is_group_divisible_design sage: TD = designs.transversal_design(4,10) sage: groups = [list(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 = [list(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([list(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([list(range(40))],[[2,2]],40,lambd=1,verbose=True) The following block has repeated elements: [2, 2] False sage: is_group_divisible_design([list(range(40))],[["e",2]],40,lambd=1,verbose=True) e does not belong to [0,...,39] False sage: is_group_divisible_design([list(range(40))],[list(range(40))],40,G=[5],lambd=1,verbose=True) a group has size 40 while G=[5] False sage: is_group_divisible_design([list(range(40))],[["e",2]],40,K=[1],lambd=1,verbose=True) a block has size 2 while K=[1] False sage: p = designs.projective_plane(3) sage: is_group_divisible_design(None, p.blocks(), 13) (True, [[0], [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12]]) sage: is_group_divisible_design(None, p.blocks()*2, 13, verbose=True) the pair (0,1) has been seen 2 times but lambda=1 False sage: is_group_divisible_design(None, p.blocks()*2, 13, lambd=2) (True, [[0], [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12]])
-
sage.combinat.designs.designs_pyx.
is_orthogonal_array
(OA, k, n, t=2, verbose=False, terminology='OA')¶ Check that the integer matrix \(OA\) is an \(OA(k,n,t)\).
See
orthogonal_array()
for a definition.INPUT:
OA
– the Orthogonal Array to be testedk,n,t
(integers) – only implemented for \(t=2\).verbose
(boolean) – whether to display some information whenOA
is not an orthogonal array \(OA(k,n)\).terminology
(string) – how to phrase the information whenverbose = True
. Possible values are \("OA"\), \("MOLS"\).
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 \(OA(3,2)\). So their number is just the cardinality of the relabeling group which is \(S_2^3 \times S_3\) and has cardinality \(48\):
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
-
sage.combinat.designs.designs_pyx.
is_pairwise_balanced_design
(blocks, v, K=None, lambd=1, verbose=False)¶ Checks that input is a Pairwise Balanced Design (PBD) on \(\{0,...,v-1\}\)
For more information on Pairwise Balanced Designs (PBD), see
PairwiseBalancedDesign
.INPUT:
blocks
– collection of blocksv
(integers) – size of the ground set assumed to be \(X=\{0,...,v-1\}\).K
– list of integers of which the sizes of the blocks must be elements. Set toNone
(automatic guess) by default.lambd
– value of \(\lambda\). Set to \(1\) by default.verbose
(boolean) – whether to display some information when the design is not a PBD.
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 = [list(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
-
sage.combinat.designs.designs_pyx.
is_projective_plane
(blocks, verbose=False)¶ Test whether the blocks form a projective plane on \(\{0,...,v-1\}\)
A projective plane is an incidence structure that has the following properties:
- Given any two distinct points, there is exactly one line incident with both of them.
- Given any two distinct lines, there is exactly one point incident with both of them.
- There are four points such that no line is incident with more than two of them.
For more informations, see Wikipedia article Projective_plane.
is_t_design()
can also check if an incidence structure is a projective plane with the parameters \(v=k^2+k+1\), \(t=2\) and \(l=1\).INPUT:
blocks
– collection of blocksverbose
– whether to print additional information
EXAMPLES:
sage: from sage.combinat.designs.designs_pyx import is_projective_plane sage: p = designs.projective_plane(4) sage: b = p.blocks() sage: is_projective_plane(b, verbose=True) True sage: p = designs.projective_plane(2) sage: b = p.blocks() sage: is_projective_plane(b) True sage: b[0][2] = 5 sage: is_projective_plane(b, verbose=True) the pair (0,5) has been seen 2 times but lambda=1 False sage: is_projective_plane([[0,1,2],[1,2,4]], verbose=True) the pair (0,3) has been seen 0 times but lambda=1 False sage: is_projective_plane([[1]], verbose=True) First block has less than 3 points. False sage: p = designs.projective_plane(2) sage: b = p.blocks() sage: b[2].append(4) sage: is_projective_plane(b, verbose=True) a block has size 4 while K=[3] False
-
sage.combinat.designs.designs_pyx.
is_quasi_difference_matrix
(M, G, k, lmbda, mu, u, verbose=False)¶ Test if the matrix is a \((G,k;\lambda,\mu;u)\)-quasi-difference matrix
Let \(G\) be an abelian group of order \(n\). A \((n,k;\lambda,\mu;u)\)-quasi-difference matrix (QDM) is a matrix \(Q_{ij}\) with \(\lambda(n-1+2u)+\mu\) rows and \(k\) columns, with each entry either equal to
None
(i.e. the ‘missing entries’) or to an element of \(G\). Each column contains exactly \(\lambda u\) empty entries, and each row contains at most oneNone
. Furthermore, for each \(1\leq i<j\leq k\), the multiset\[\{q_{li}-q_{lj}:1\leq l\leq \lambda (n-1+2u)+\mu, \text{ with } q_{li}\text{ and }q_{lj}\text{ not empty}\}\]contains \(\lambda\) times every nonzero element of \(G\) and contains \(\mu\) times \(0\).
INPUT:
M
– a matrix with entries fromG
(or equal toNone
for missing entries)G
– a groupk,lmbda,mu,u
– integersverbose
(boolean) – whether to print some information when the answer isFalse
.
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(list(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