Cython functions for combinatorial designs#
This module implements the design methods that need to be somewhat efficient.
Functions#
- sage.combinat.designs.designs_pyx.is_covering_array(array, strength=None, levels=None, verbose=False, parameters=False)#
Check if the input is a covering array with given strength.
See
sage.combinat.designs.covering_arrayfor a definition.INPUT:
array– the Covering Array to be tested.strength(integer) – the parameter \(t\) of the covering array, such that in any selection of \(t\) columns of the array, every \(t\) -tuple appears at least once. If set to None then all t > 0 are tested to and the maximal strength is used.levels– the number of symbols that appear inarray. If set to None, then each unique entry inarrayis counted.verbose(boolean) – whether to display some information about the covering array.parameters(boolean) – whether to return the parameters of the Covering Array. If set toTrue, the function returns a pair(boolean_answer,(N,t,k,v)).
EXAMPLES:
sage: from sage.combinat.designs.designs_pyx import is_covering_array sage: C = [[1, 1, 1, 0], ....: [1, 1, 0, 0], ....: [0, 0, 0]] sage: is_covering_array(C) Traceback (most recent call last): ... ValueError: Not all rows are the same length, row 2 is not the same length as row 0 sage: C = [[0, 1, 1], ....: [1, 1, 0], ....: [1, 0, 1], ....: [0, 0, 0,]] sage: is_covering_array(C,strength=4) Traceback (most recent call last): ... ValueError: Strength must be equal or less than number of columns sage: C = [[0, 1, 1], ....: [1, 1, 1], ....: [1, 0, 1]] sage: is_covering_array(C,verbose=True) A 3 by 3 Covering Array with strength 0 with entries from a symbol set of size 2 True sage: C = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], ....: [0, 0, 0, 0, 1, 1, 1, 1, 1, 1], ....: [0, 1, 1, 1, 0, 0, 0, 1, 1, 1], ....: [1, 0, 1, 1, 0, 1, 1, 0, 0, 1], ....: [1, 1, 0, 1, 1, 0, 1, 0, 1, 0], ....: [1, 1, 1, 0, 1, 1, 0, 1, 2, 0]] sage: is_covering_array(C,levels=2) Traceback (most recent call last): ... ValueError: Array should contain integer symbols from 0 to 1 sage: C = [[1, 0, 0, 2, 0, 2, 1, 2, 2, 1, 0, 2, 2], ....: [1, 1, 0, 0, 2, 0, 2, 1, 2, 2, 1, 0, 2], ....: [1, 1, 1, 0, 0, 2, 0, 2, 1, 2, 2, 1, 0], ....: [0, 1, 1, 1, 0, 0, 2, 0, 2, 1, 2, 2, 1], ....: [2, 0, 1, 1, 1, 0, 0, 2, 0, 2, 1, 2, 2], ....: [1, 2, 0, 1, 1, 1, 0, 0, 2, 0, 2, 1, 2], ....: [1, 1, 2, 0, 1, 1, 1, 0, 0, 2, 0, 2, 1], ....: [2, 1, 1, 2, 0, 1, 1, 1, 0, 0, 2, 0, 2], ....: [1, 2, 1, 1, 2, 0, 1, 1, 1, 0, 0, 2, 0], ....: [0, 1, 2, 1, 1, 2, 0, 1, 1, 1, 0, 0, 2], ....: [1, 0, 1, 2, 1, 1, 2, 0, 1, 1, 1, 0, 0], ....: [0, 1, 0, 1, 2, 1, 1, 2, 0, 1, 1, 1, 0], ....: [0, 0, 1, 0, 1, 2, 1, 1, 2, 0, 1, 1, 1], ....: [2, 0, 0, 1, 0, 1, 2, 1, 1, 2, 0, 1, 1], ....: [2, 2, 0, 0, 1, 0, 1, 2, 1, 1, 2, 0, 1], ....: [2, 2, 2, 0, 0, 1, 0, 1, 2, 1, 1, 2, 0], ....: [0, 2, 2, 2, 0, 0, 1, 0, 1, 2, 1, 1, 2], ....: [1, 0, 2, 2, 2, 0, 0, 1, 0, 1, 2, 1, 1], ....: [2, 1, 0, 2, 2, 2, 0, 0, 1, 0, 1, 2, 1], ....: [2, 2, 1, 0, 2, 2, 2, 0, 0, 1, 0, 1, 2], ....: [1, 2, 2, 1, 0, 2, 2, 2, 0, 0, 1, 0, 1], ....: [2, 1, 2, 2, 1, 0, 2, 2, 2, 0, 0, 1, 0], ....: [0, 2, 1, 2, 2, 1, 0, 2, 2, 2, 0, 0, 1], ....: [2, 0, 2, 1, 2, 2, 1, 0, 2, 2, 2, 0, 0], ....: [0, 2, 0, 2, 1, 2, 2, 1, 0, 2, 2, 2, 0], ....: [0, 0, 2, 0, 2, 1, 2, 2, 1, 0, 2, 2, 2], ....: [1, 1, 0, 2, 1, 1, 2, 1, 0, 1, 0, 0, 2], ....: [1, 1, 1, 0, 2, 1, 1, 2, 1, 0, 1, 0, 0], ....: [0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 0, 1, 0], ....: [0, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 0, 1], ....: [2, 0, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 0], ....: [0, 2, 0, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1], ....: [2, 0, 2, 0, 0, 1, 1, 1, 0, 2, 1, 1, 2], ....: [1, 2, 0, 2, 0, 0, 1, 1, 1, 0, 2, 1, 1], ....: [2, 1, 2, 0, 2, 0, 0, 1, 1, 1, 0, 2, 1], ....: [2, 2, 1, 2, 0, 2, 0, 0, 1, 1, 1, 0, 2], ....: [1, 2, 2, 1, 2, 0, 2, 0, 0, 1, 1, 1, 0], ....: [0, 1, 2, 2, 1, 2, 0, 2, 0, 0, 1, 1, 1], ....: [2, 0, 1, 2, 2, 1, 2, 0, 2, 0, 0, 1, 1], ....: [2, 2, 0, 1, 2, 2, 1, 2, 0, 2, 0, 0, 1], ....: [2, 2, 2, 0, 1, 2, 2, 1, 2, 0, 2, 0, 0], ....: [0, 2, 2, 2, 0, 1, 2, 2, 1, 2, 0, 2, 0], ....: [0, 0, 2, 2, 2, 0, 1, 2, 2, 1, 2, 0, 2], ....: [1, 0, 0, 2, 2, 2, 0, 1, 2, 2, 1, 2, 0], ....: [0, 1, 0, 0, 2, 2, 2, 0, 1, 2, 2, 1, 2], ....: [1, 0, 1, 0, 0, 2, 2, 2, 0, 1, 2, 2, 1], ....: [2, 1, 0, 1, 0, 0, 2, 2, 2, 0, 1, 2, 2], ....: [1, 2, 1, 0, 1, 0, 0, 2, 2, 2, 0, 1, 2], ....: [1, 1, 2, 1, 0, 1, 0, 0, 2, 2, 2, 0, 1], ....: [2, 1, 1, 2, 1, 0, 1, 0, 0, 2, 2, 2, 0], ....: [0, 2, 1, 1, 2, 1, 0, 1, 0, 0, 2, 2, 2], ....: [1, 0, 2, 1, 1, 2, 1, 0, 1, 0, 0, 2, 2], ....: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] sage: is_covering_array(C,parameters=True) (True, (53, 3, 13, 3)) sage: C = [[1, 0, 1, 1, 2, 0, 2, 2], ....: [2, 1, 0, 1, 1, 2, 0, 2], ....: [2, 2, 1, 0, 1, 1, 2, 0], ....: [0, 2, 2, 1, 0, 1, 1, 2], ....: [2, 0, 2, 2, 1, 0, 1, 1], ....: [1, 2, 0, 2, 2, 1, 0, 1], ....: [1, 1, 2, 0, 2, 2, 1, 0], ....: [0, 1, 1, 2, 0, 2, 2, 1]] sage: is_covering_array(C,strength=2,parameters=True) (False, (8, 0, 8, 3))
- 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 fromGG– 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 toNonethe groups are guessed automatically, and the function returns(True, guessed_groups)instead ofTrueblocks– 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 whenOAis 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 toNonefor 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