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)[source]

Check if the input is a covering array with given strength.

See sage.combinat.designs.covering_array for 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 in array If set to None, then each unique entry in array is 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 to True, 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))

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_covering_array
>>> C = [[Integer(1), Integer(1), Integer(1), Integer(0)],
...      [Integer(1), Integer(1), Integer(0), Integer(0)],
...      [Integer(0), Integer(0), Integer(0)]]
>>> 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

>>> C = [[Integer(0), Integer(1), Integer(1)],
...      [Integer(1), Integer(1), Integer(0)],
...      [Integer(1), Integer(0), Integer(1)],
...      [Integer(0), Integer(0), Integer(0),]]
>>> is_covering_array(C,strength=Integer(4))
Traceback (most recent call last):
...
ValueError: Strength must be equal or less than number of columns

>>> C = [[Integer(0), Integer(1), Integer(1)],
...      [Integer(1), Integer(1), Integer(1)],
...      [Integer(1), Integer(0), Integer(1)]]
>>> 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

>>> C = [[Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...      [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(1), Integer(1), Integer(1)],
...      [Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1)],
...      [Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(1)],
...      [Integer(1), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(1), Integer(0)],
...      [Integer(1), Integer(1), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(2), Integer(0)]]
>>> is_covering_array(C,levels=Integer(2))
Traceback (most recent call last):
...
ValueError: Array should contain integer symbols from 0 to 1

>>> C = [[Integer(1), Integer(0), Integer(0), Integer(2), Integer(0), Integer(2), Integer(1), Integer(2), Integer(2), Integer(1), Integer(0), Integer(2), Integer(2)],
...      [Integer(1), Integer(1), Integer(0), Integer(0), Integer(2), Integer(0), Integer(2), Integer(1), Integer(2), Integer(2), Integer(1), Integer(0), Integer(2)],
...      [Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(2), Integer(0), Integer(2), Integer(1), Integer(2), Integer(2), Integer(1), Integer(0)],
...      [Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(2), Integer(0), Integer(2), Integer(1), Integer(2), Integer(2), Integer(1)],
...      [Integer(2), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(2), Integer(0), Integer(2), Integer(1), Integer(2), Integer(2)],
...      [Integer(1), Integer(2), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(2), Integer(0), Integer(2), Integer(1), Integer(2)],
...      [Integer(1), Integer(1), Integer(2), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(2), Integer(0), Integer(2), Integer(1)],
...      [Integer(2), Integer(1), Integer(1), Integer(2), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(2), Integer(0), Integer(2)],
...      [Integer(1), Integer(2), Integer(1), Integer(1), Integer(2), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(2), Integer(0)],
...      [Integer(0), Integer(1), Integer(2), Integer(1), Integer(1), Integer(2), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(2)],
...      [Integer(1), Integer(0), Integer(1), Integer(2), Integer(1), Integer(1), Integer(2), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)],
...      [Integer(0), Integer(1), Integer(0), Integer(1), Integer(2), Integer(1), Integer(1), Integer(2), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0)],
...      [Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(2), Integer(1), Integer(1), Integer(2), Integer(0), Integer(1), Integer(1), Integer(1)],
...      [Integer(2), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(2), Integer(1), Integer(1), Integer(2), Integer(0), Integer(1), Integer(1)],
...      [Integer(2), Integer(2), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(2), Integer(1), Integer(1), Integer(2), Integer(0), Integer(1)],
...      [Integer(2), Integer(2), Integer(2), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(2), Integer(1), Integer(1), Integer(2), Integer(0)],
...      [Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(2), Integer(1), Integer(1), Integer(2)],
...      [Integer(1), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(2), Integer(1), Integer(1)],
...      [Integer(2), Integer(1), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(2), Integer(1)],
...      [Integer(2), Integer(2), Integer(1), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(2)],
...      [Integer(1), Integer(2), Integer(2), Integer(1), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1)],
...      [Integer(2), Integer(1), Integer(2), Integer(2), Integer(1), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(0), Integer(1), Integer(0)],
...      [Integer(0), Integer(2), Integer(1), Integer(2), Integer(2), Integer(1), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(0), Integer(1)],
...      [Integer(2), Integer(0), Integer(2), Integer(1), Integer(2), Integer(2), Integer(1), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(0)],
...      [Integer(0), Integer(2), Integer(0), Integer(2), Integer(1), Integer(2), Integer(2), Integer(1), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0)],
...      [Integer(0), Integer(0), Integer(2), Integer(0), Integer(2), Integer(1), Integer(2), Integer(2), Integer(1), Integer(0), Integer(2), Integer(2), Integer(2)],
...      [Integer(1), Integer(1), Integer(0), Integer(2), Integer(1), Integer(1), Integer(2), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(2)],
...      [Integer(1), Integer(1), Integer(1), Integer(0), Integer(2), Integer(1), Integer(1), Integer(2), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)],
...      [Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(2), Integer(1), Integer(1), Integer(2), Integer(1), Integer(0), Integer(1), Integer(0)],
...      [Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(2), Integer(1), Integer(1), Integer(2), Integer(1), Integer(0), Integer(1)],
...      [Integer(2), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(2), Integer(1), Integer(1), Integer(2), Integer(1), Integer(0)],
...      [Integer(0), Integer(2), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(2), Integer(1), Integer(1), Integer(2), Integer(1)],
...      [Integer(2), Integer(0), Integer(2), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(2), Integer(1), Integer(1), Integer(2)],
...      [Integer(1), Integer(2), Integer(0), Integer(2), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(2), Integer(1), Integer(1)],
...      [Integer(2), Integer(1), Integer(2), Integer(0), Integer(2), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(2), Integer(1)],
...      [Integer(2), Integer(2), Integer(1), Integer(2), Integer(0), Integer(2), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(2)],
...      [Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(0), Integer(2), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0)],
...      [Integer(0), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(0), Integer(2), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1)],
...      [Integer(2), Integer(0), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(0), Integer(2), Integer(0), Integer(0), Integer(1), Integer(1)],
...      [Integer(2), Integer(2), Integer(0), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(0), Integer(2), Integer(0), Integer(0), Integer(1)],
...      [Integer(2), Integer(2), Integer(2), Integer(0), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(0), Integer(2), Integer(0), Integer(0)],
...      [Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(0), Integer(2), Integer(0)],
...      [Integer(0), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(0), Integer(2)],
...      [Integer(1), Integer(0), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2), Integer(0)],
...      [Integer(0), Integer(1), Integer(0), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(1), Integer(2), Integer(2), Integer(1), Integer(2)],
...      [Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(1), Integer(2), Integer(2), Integer(1)],
...      [Integer(2), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(1), Integer(2), Integer(2)],
...      [Integer(1), Integer(2), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(1), Integer(2)],
...      [Integer(1), Integer(1), Integer(2), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0), Integer(1)],
...      [Integer(2), Integer(1), Integer(1), Integer(2), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(2), Integer(2), Integer(2), Integer(0)],
...      [Integer(0), Integer(2), Integer(1), Integer(1), Integer(2), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(2), Integer(2), Integer(2)],
...      [Integer(1), Integer(0), Integer(2), Integer(1), Integer(1), Integer(2), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(2), Integer(2)],
...      [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)]]
>>> is_covering_array(C,parameters=True)
(True, (53, 3, 13, 3))

>>> C = [[Integer(1), Integer(0), Integer(1), Integer(1), Integer(2), Integer(0), Integer(2), Integer(2)],
...      [Integer(2), Integer(1), Integer(0), Integer(1), Integer(1), Integer(2), Integer(0), Integer(2)],
...      [Integer(2), Integer(2), Integer(1), Integer(0), Integer(1), Integer(1), Integer(2), Integer(0)],
...      [Integer(0), Integer(2), Integer(2), Integer(1), Integer(0), Integer(1), Integer(1), Integer(2)],
...      [Integer(2), Integer(0), Integer(2), Integer(2), Integer(1), Integer(0), Integer(1), Integer(1)],
...      [Integer(1), Integer(2), Integer(0), Integer(2), Integer(2), Integer(1), Integer(0), Integer(1)],
...      [Integer(1), Integer(1), Integer(2), Integer(0), Integer(2), Integer(2), Integer(1), Integer(0)],
...      [Integer(0), Integer(1), Integer(1), Integer(2), Integer(0), Integer(2), Integer(2), Integer(1)]]
>>> is_covering_array(C,strength=Integer(2),parameters=True)
(False, (8, 0, 8, 3))
sage.combinat.designs.designs_pyx.is_difference_matrix(M, G, k, lmbda=1, verbose=False)[source]

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 (default: \(1\))

  • 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')                                                             # 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

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_difference_matrix
>>> q = Integer(3)**Integer(3)
>>> F = GF(q,'x')                                                             # needs sage.rings.finite_rings
>>> M = [[x*y for y in F] for x in F]                                         # needs sage.rings.finite_rings
>>> is_difference_matrix(M,F,q,verbose=Integer(1))                                     # needs sage.rings.finite_rings
True

>>> B = [[Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...      [Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(2), Integer(3), Integer(4), Integer(0), Integer(1)],
...      [Integer(0), Integer(2), Integer(4), Integer(1), Integer(3), Integer(3), Integer(0), Integer(2), Integer(4), Integer(1)]]
>>> G = GF(Integer(5))
>>> B = [[G(b) for b in R] for R in B]
>>> is_difference_matrix(list(zip(*B)),G,Integer(3),Integer(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

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> for R in M: R.append(None)
>>> is_difference_matrix(M,F,q,verbose=Integer(1))
The matrix has 28 columns but k=27
False
>>> for R in M: _=R.pop(-Integer(1))
>>> M.append([None]*Integer(3)**Integer(3))
>>> is_difference_matrix(M,F,q,verbose=Integer(1))
The matrix has 28 rows instead of lambda(|G|-1+2u)+mu=1(27-1+2.0)+1=27
False
>>> _= M.pop(-Integer(1))
>>> for R in M: R[-Integer(1)] = Integer(0)
>>> is_difference_matrix(M,F,q,verbose=Integer(1))
Columns 0 and 26 generate 0 exactly 27 times instead of the expected mu(=1)
False
>>> for R in M: R[-Integer(1)] = Integer(1)
>>> M[-Integer(1)][-Integer(1)] = Integer(0)
>>> is_difference_matrix(M,F,q,verbose=Integer(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)[source]

Check that input is a Group Divisible Design on \(\{0, \ldots, v-1\}\).

For more information on Group Divisible Designs, see GroupDivisibleDesign.

INPUT:

  • groups – a partition of \(X\). If set to None the groups are guessed automatically, and the function returns (True, guessed_groups) instead of True

  • 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)                                     # 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

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_group_divisible_design
>>> TD = designs.transversal_design(Integer(4),Integer(10))                                     # needs sage.modules
>>> groups = [list(range(i*Integer(10),(i+Integer(1))*Integer(10))) for i in range(Integer(4))]
>>> is_group_divisible_design(groups,TD,Integer(40),lambd=Integer(1))                           # needs sage.modules
True
sage.combinat.designs.designs_pyx.is_orthogonal_array(OA, k, n, t=2, verbose=False, terminology='OA')[source]

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: # 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

>>> from sage.all import *
>>> # needs sage.schemes
>>> from sage.combinat.designs.designs_pyx import is_orthogonal_array
>>> OA = designs.orthogonal_arrays.build(Integer(8),Integer(9))
>>> is_orthogonal_array(OA,Integer(8),Integer(9))
True
>>> is_orthogonal_array(OA,Integer(8),Integer(10))
False
>>> OA[Integer(4)][Integer(3)] = Integer(1)
>>> is_orthogonal_array(OA,Integer(8),Integer(9))
False
>>> is_orthogonal_array(OA,Integer(8),Integer(9),verbose=True)
Columns 0 and 3 are not orthogonal
False
>>> is_orthogonal_array(OA,Integer(8),Integer(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)[source]

Check that input is a Pairwise Balanced Design (PBD) on \(\{0, \ldots, 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\) (default: \(1\))

  • 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

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_pairwise_balanced_design
>>> sts = designs.steiner_triple_system(Integer(9))
>>> is_pairwise_balanced_design(sts,Integer(9),[Integer(3)],Integer(1))
True
>>> TD = designs.transversal_design(Integer(4),Integer(10)).blocks()                            # needs sage.modules
>>> groups = [list(range(i*Integer(10),(i+Integer(1))*Integer(10))) for i in range(Integer(4))]
>>> is_pairwise_balanced_design(TD + groups, Integer(40), [Integer(4),Integer(10)], Integer(1), verbose=True)     # needs sage.modules
True
sage.combinat.designs.designs_pyx.is_projective_plane(blocks, verbose=False)[source]

Test whether the blocks form a projective plane on \(\{0,...,v-1\}\).

A projective plane is an incidence structure that has the following properties:

  1. Given any two distinct points, there is exactly one line incident with both of them.

  2. Given any two distinct lines, there is exactly one point incident with both of them.

  3. 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 blocks

  • verbose – 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

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_projective_plane
>>> p = designs.projective_plane(Integer(4))                                           # needs sage.schemes
>>> b = p.blocks()                                                            # needs sage.schemes
>>> is_projective_plane(b, verbose=True)                                      # needs sage.schemes
True

>>> # needs sage.schemes
>>> p = designs.projective_plane(Integer(2))
>>> b = p.blocks()
>>> is_projective_plane(b)
True
>>> b[Integer(0)][Integer(2)] = Integer(5)
>>> is_projective_plane(b, verbose=True)
the pair (0,5) has been seen 2 times but lambda=1
False

>>> is_projective_plane([[Integer(0),Integer(1),Integer(2)],[Integer(1),Integer(2),Integer(4)]], verbose=True)
the pair (0,3) has been seen 0 times but lambda=1
False

>>> is_projective_plane([[Integer(1)]], verbose=True)
First block has less than 3 points.
False

>>> # needs sage.schemes
>>> p = designs.projective_plane(Integer(2))
>>> b = p.blocks()
>>> b[Integer(2)].append(Integer(4))
>>> 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)[source]

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')                                                             # 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

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_quasi_difference_matrix
>>> q = Integer(3)**Integer(3)
>>> F = GF(q,'x')                                                             # needs sage.rings.finite_rings
>>> M = [[x*y for y in F] for x in F]                                         # needs sage.rings.finite_rings
>>> is_quasi_difference_matrix(M,F,q,Integer(1),Integer(1),Integer(0),verbose=Integer(1))                         # needs sage.rings.finite_rings
True

>>> B = [[Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...      [Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(2), Integer(3), Integer(4), Integer(0), Integer(1)],
...      [Integer(0), Integer(2), Integer(4), Integer(1), Integer(3), Integer(3), Integer(0), Integer(2), Integer(4), Integer(1)]]
>>> G = GF(Integer(5))
>>> B = [[G(b) for b in R] for R in B]
>>> is_quasi_difference_matrix(list(zip(*B)),G,Integer(3),Integer(2),Integer(2),Integer(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

>>> from sage.all import *
>>> from sage.combinat.designs.database import QDM
>>> G,M = QDM[Integer(38),Integer(1)][Integer(37),Integer(1),Integer(1),Integer(1)][Integer(1)]()
>>> is_quasi_difference_matrix(M,G,k=Integer(6),lmbda=Integer(1),mu=Integer(1),u=Integer(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

>>> from sage.all import *
>>> is_quasi_difference_matrix(M,G,k=Integer(6),lmbda=Integer(1),mu=Integer(1),u=Integer(3),verbose=Integer(1))
The matrix has 39 rows instead of lambda(|G|-1+2u)+mu=1(37-1+2.3)+1=43
False
>>> is_quasi_difference_matrix(M,G,k=Integer(6),lmbda=Integer(1),mu=Integer(2),u=Integer(1),verbose=Integer(1))
The matrix has 39 rows instead of lambda(|G|-1+2u)+mu=1(37-1+2.1)+2=40
False
>>> M[Integer(3)][Integer(1)] = None
>>> is_quasi_difference_matrix(M,G,k=Integer(6),lmbda=Integer(1),mu=Integer(1),u=Integer(1),verbose=Integer(1))
Row 3 contains more than one empty entry
False
>>> M[Integer(3)][Integer(1)] = Integer(1)
>>> M[Integer(6)][Integer(1)] = None
>>> is_quasi_difference_matrix(M,G,k=Integer(6),lmbda=Integer(1),mu=Integer(1),u=Integer(1),verbose=Integer(1))
Column 1 contains 2 empty entries instead of the expected lambda.u=1.1=1
False