Cython functions for combinatorial designs

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 from G
  • G – a group
  • k – integer
  • lmbda (integer) – set to 1 by default.
  • verbose (boolean) – whether to print some information when the answer is False.

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
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
  • blocks – collection of blocks
  • v (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 to None (automatic guess) by default.
  • K – list of integers of which the sizes of the blocks must be elements. Set to None (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 = [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
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 tested
  • k,n,t (integers) – only implemented for t=2.
  • verbose (boolean) – whether to display some information when OA is not an orthogonal array OA(k,n).
  • terminology (string) – how to phrase the information when verbose = 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 blocks
  • v (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 to None (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 = [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_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 one None. 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 from G (or equal to None for missing entries)
  • G – a group
  • k,lmbda,mu,u – integers
  • verbose (boolean) – whether to print some information when the answer is False.

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

Table Of Contents

Previous topic

Catalog of designs

Next topic

Difference families

This Page