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') # needs sage.rings.finite_rings sage: M = [[x*y for y in F] for x in F] # needs sage.rings.finite_rings sage: is_difference_matrix(M,F,q,verbose=1) # needs sage.rings.finite_rings 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: # needs sage.rings.finite_rings 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) # needs sage.modules sage: groups = [list(range(i*10,(i+1)*10)) for i in range(4)] sage: is_group_divisible_design(groups,TD,40,lambd=1) # needs sage.modules True
- 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: # needs sage.schemes 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
- 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() # needs sage.modules 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) # needs sage.modules True
- 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) # needs sage.schemes sage: b = p.blocks() # needs sage.schemes sage: is_projective_plane(b, verbose=True) # needs sage.schemes True sage: # needs sage.schemes 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: # needs sage.schemes 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') # needs sage.rings.finite_rings sage: M = [[x*y for y in F] for x in F] # needs sage.rings.finite_rings sage: is_quasi_difference_matrix(M,F,q,1,1,0,verbose=1) # needs sage.rings.finite_rings 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