This module gathers everything related to orthogonal arrays (or transversal
designs). One can build an (or check that it can be built) with
orthogonal_array():
sage: OA = designs.orthogonal_array(4,8)
It defines the following functions:
orthogonal_array() | Return an orthogonal array of parameters ![]() |
transversal_design() | Return a transversal design of parameters ![]() |
incomplete_orthogonal_array() | Return an ![]() |
is_transversal_design() | Check that a given set of blocks B is a transversal design. |
is_orthogonal_array() | Check that the integer matrix ![]() ![]() |
wilson_construction() | Return a ![]() ![]() |
TD_product() | Return the product of two transversal designs. |
OA_find_disjoint_blocks() | Return ![]() ![]() |
OA_relabel() | Return a relabelled version of the OA. |
OA_from_quasi_difference_matrix() | Return an Orthogonal Array from a Quasi-Difference matrix |
OA_from_Vmt() | Return an Orthogonal Array from a ![]() |
OA_from_PBD() | Return an ![]() |
OA_from_wider_OA() | Return the first ![]() ![]() |
Todo
REFERENCES:
[CD96] | Making the MOLS table Charles Colbourn and Jeffrey Dinitz Computational and constructive design theory vol 368,pages 67-134 1996 |
Return disjoint blocks contained in a given
.
blocks of an
are said to be disjoint if they all have
different values for a every given index, i.e. if they correspond to
disjoint blocks in the
assciated with the
.
INPUT:
See also
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays import OA_find_disjoint_blocks
sage: k=3;n=4;x=3
sage: Bs = OA_find_disjoint_blocks(designs.orthogonal_array(k,n),k,n,x)
sage: assert len(Bs) == x
sage: for i in range(k):
....: assert len(set([B[i] for B in Bs])) == x
sage: OA_find_disjoint_blocks(designs.orthogonal_array(k,n),k,n,5)
Traceback (most recent call last):
...
ValueError: There does not exist 5 disjoint blocks in this OA(3,4)
Return an from a PBD
Construction
Let be a
-PBD. If there exists for every
a
(i.e. if there exist
idempotent MOLS), then
one can obtain a
by concatenating:
Note
This function raises an exception when Sage is unable to build the necessary designs.
INPUT:
EXAMPLES:
We start from the example VI.1.2 from the [DesignHandbook] to build an
:
sage: from sage.combinat.designs.orthogonal_arrays import OA_from_PBD
sage: from sage.combinat.designs.designs_pyx import is_orthogonal_array
sage: pbd = [[0,1,2,3],[0,4,5,6],[0,7,8,9],[1,4,7],[1,5,8],
....: [1,6,9],[2,4,9],[2,5,7],[2,6,8],[3,4,8],[3,5,9],[3,6,7]]
sage: oa = OA_from_PBD(3,10,pbd)
sage: is_orthogonal_array(oa, 3, 10)
True
But we cannot build an :
sage: OA_from_PBD(4,10,pbd)
Traceback (most recent call last):
...
EmptySetError: There is no OA(n+1,n) - 3.OA(n+1,1) as all blocks do intersect in a projective plane.
Or an :
sage: _ = OA_from_PBD(3,6,pbd)
Traceback (most recent call last):
...
RuntimeError: The PBD covers a point 8 which is not in {0, ..., 5}
Return an Orthogonal Array from a
Definition
Let be a prime power and let
for
integers. Let
be a primitive element of
. A
vector is a vector
for which, for each
, the differences
represent the cyclotomic classes of
(compute subscripts
modulo
). In other words, for fixed
, is
and
then
Construction of a quasi-difference matrix from a `V(m,t)` vector
Starting with a vector
, form a single column
of length
whose first entry is empty, and whose remaining entries are
. Form
columns by multiplying this column by the
th roots, i.e. the powers of
. From each of these
columns,
form
columns by taking the
cyclic shifts of the column. The
result is a
.
For more information, refer to the Handbook of Combinatorial Designs [DesignHandbook].
INPUT:
See also
EXAMPLES:
sage: _ = designs.orthogonal_array(6,46) # indirect doctest
Return an Orthogonal Array from a Quasi-Difference matrix
Difference Matrices
Let be a group of order
. A difference matrix
is a
matrix with entries from
such that for any
the set
is equal to
.
By concatenating the matrices
(where
), one obtains a
matrix of size
which is also an
.
Quasi-difference Matrices
A quasi-difference matrix is a difference matrix with missing entries. The
construction above can be applied again in this case, where the missing
entries in each column of are replaced by unique values on which
has
a trivial action.
This produces an incomplete orthogonal array with a “hole” (i.e. missing
rows) of size ‘u’ (i.e. the number of missing values per row of ). If
there exists an
, then adding the rows of this
to the
incomplete orthogonal array should lead to an OA...
Formal definition (from the Handbook of Combinatorial Designs [DesignHandbook])
Let be an abelian group of order
. A
-quasi-difference matrix (QDM) is a matrix
with
rows and
columns, with each entry either
empty or containing an element of
. Each row contains exactly
entries, and each column contains at most one empty entry. Furthermore, for
each
the multiset
contains every nonzero element of exactly
times, and contains
0 exactly
times.
Construction
If a -QDM exists and
, then an
exists. Start with a
-QDM
over the group
. Append
columns of zeroes. Then select
elements
not in
, and replace the empty
entries, each by one of these infinite symbols, so that
appears
exactly once in each row. Develop the resulting matrix over the group
(leaving infinite symbols fixed), to obtain a
matrix
. Then
is an orthogonal array with
rows and index
, having
symbols and one hole of size
.
Adding to an
with elements
yields
the
.
For more information, see the Handbook of Combinatorial Designs [DesignHandbook] or http://web.cs.du.edu/~petr/milehigh/2013/Colbourn.pdf.
INPUT:
EXAMPLES:
sage: _ = designs.orthogonal_array(6,20,2) # indirect doctest
Return the first columns of
.
If has
columns, this function returns
immediately.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays import OA_from_wider_OA
sage: OA_from_wider_OA(designs.orthogonal_array(6,20,2),1)[:5]
[(19,), (0,), (0,), (7,), (1,)]
sage: _ = designs.orthogonal_array(5,46) # indirect doctest
Return a relabelled version of the OA.
INPUT:
OA – an OA, or rather a list of blocks of length , each
of which contains integers from
to
.
k,n (integers)
blocks (list of blocks) – relabels the integers of the OA
from into
in such a way that the
blocks from block are respectively relabeled as
[n-i,...,n-i], ..., [n-1,...,n-1]. Thus, the blocks from
this list are expected to have disjoint values for each
coordinate.
If set to the empty list (default) no such relabelling is performed.
matrix – a matrix of dimensions such that if the i th
coordinate of a block is
, this
will be relabelled with
matrix[i][x]. This is not necessarily an integer between
and
, and it is not necessarily an integer either. This is
performed after the previous relabelling.
If set to None (default) no such relabelling is performed.
Note
A None coordinate in one block remains a None coordinate in the final block.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays import OA_relabel
sage: OA = designs.orthogonal_array(3,2)
sage: OA_relabel(OA,3,2,matrix=[["A","B"],["C","D"],["E","F"]])
[['A', 'C', 'E'], ['A', 'D', 'F'], ['B', 'C', 'F'], ['B', 'D', 'E']]
sage: TD = OA_relabel(OA,3,2,matrix=[[0,1],[2,3],[4,5]]); TD
[[0, 2, 4], [0, 3, 5], [1, 2, 5], [1, 3, 4]]
sage: from sage.combinat.designs.orthogonal_arrays import is_transversal_design
sage: is_transversal_design(TD,3,2)
True
Making sure that [2,2,2,2] is a block of . We do this
by relabelling block [0,0,0,0] which belongs to the design:
sage: designs.orthogonal_array(4,3)
[[0, 0, 0, 0], [0, 1, 2, 1], [0, 2, 1, 2], [1, 0, 2, 2], [1, 1, 1, 0], [1, 2, 0, 1], [2, 0, 1, 1], [2, 1, 0, 2], [2, 2, 2, 0]]
sage: OA_relabel(designs.orthogonal_array(4,3),4,3,blocks=[[0,0,0,0]])
[[2, 2, 2, 2], [2, 0, 1, 0], [2, 1, 0, 1], [0, 2, 1, 1], [0, 0, 0, 2], [0, 1, 2, 0], [1, 2, 0, 0], [1, 0, 2, 1], [1, 1, 1, 2]]
TESTS:
sage: OA_relabel(designs.orthogonal_array(3,2),3,2,blocks=[[0,1],[0,1]])
Traceback (most recent call last):
...
RuntimeError: Two block have the same coordinate for one of the k dimensions
Return the product of two transversal designs.
From a transversal design of parameters
and a transversal
design
of parameters
, this function returns a transversal
design of parameters
where
.
Formally, if the groups of are
and the groups of
are
, the groups of the product design are
and its blocks are the
where
is a
block of
and
is a block of
.
INPUT:
Note
This function uses transversal designs with
both as input and
ouptut.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays import TD_product
sage: TD1 = designs.transversal_design(6,7)
sage: TD2 = designs.transversal_design(6,12)
sage: TD6_84 = TD_product(6,TD1,7,TD2,12)
Return an .
An is an orthogonal array from
which have been removed disjoint
. So it can
exist only if a
exists.
A very useful particular case (see e.g. the Wilson construction in
wilson_construction()) is when all . In that case the
incomplete design is a
. Such design is equivalent to
transversal design
from which has been removed
disjoint
blocks. This specific case is the only one available through this function
at the moment.
INPUT:
k,n (integers)
holes_sizes (list of integers) – respective sizes of the holes to be found.
Note
Right now the feature is only available when all holes have size 1,
i.e. .
existence (boolean) – instead of building the design, return:
- True – meaning that Sage knows how to build the design
- Unknown – meaning that Sage does not know how to build the design, but that the design may exist (see sage.misc.unknown).
- False – meaning that the design does not exist.
Note
By convention, the ground set is always and the
holes are
,
, etc.
See also
EXAMPLES:
sage: IOA = designs.incomplete_orthogonal_array(3,3,[1,1,1])
sage: IOA
[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
sage: missing_blocks = [[0,0,0],[1,1,1],[2,2,2]]
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array
sage: is_orthogonal_array(IOA + missing_blocks,3,3,2)
True
TESTS:
Affine planes and projective planes:
sage: for q in xrange(2,100):
....: if is_prime_power(q):
....: assert designs.incomplete_orthogonal_array(q,q,[1]*q,existence=True)
....: assert not designs.incomplete_orthogonal_array(q+1,q,[1]*2,existence=True)
Further tests:
sage: designs.incomplete_orthogonal_array(8,4,[1,1,1],existence=True)
False
sage: designs.incomplete_orthogonal_array(5,10,[1,1,1],existence=True)
Unknown
sage: designs.incomplete_orthogonal_array(5,10,[1,1,1])
Traceback (most recent call last):
...
NotImplementedError: I don't know how to build an OA(5,10)!
sage: designs.incomplete_orthogonal_array(4,3,[1,1])
Traceback (most recent call last):
...
EmptySetError: There is no OA(n+1,n) - 2.OA(n+1,1) as all blocks do
intersect in a projective plane.
sage: n=10
sage: k=designs.orthogonal_array(None,n,existence=True)
sage: designs.incomplete_orthogonal_array(k,n,[1,1,1],existence=True)
True
sage: _ = designs.incomplete_orthogonal_array(k,n,[1,1,1])
sage: _ = designs.incomplete_orthogonal_array(k,n,[1])
REFERENCES:
[BvR82] | More mutually orthogonal Latin squares, Andries Brouwer and John van Rees Discrete Mathematics vol.39, num.3, pages 263-281 1982 |
Check that a given set of blocks B is a transversal design.
See transversal_design() for a definition.
INPUT:
Note
The tranversal design must have as a ground set,
partitioned as
sets of size
:
.
EXAMPLES:
sage: TD = designs.transversal_design(5, 5, check=True) # indirect doctest
sage: from sage.combinat.designs.orthogonal_arrays import is_transversal_design
sage: is_transversal_design(TD, 5, 5)
True
sage: is_transversal_design(TD, 4, 4)
False
Return an orthogonal array of parameters .
An orthogonal array of parameters is a matrix with
columns
filled with integers from
in such a way that for any
columns, each
of the
possible rows occurs exactly once. In
particular, the matrix has
rows.
More general definitions sometimes involve a parameter, and we
assume here that
.
For more information on orthogonal arrays, see Wikipedia article Orthogonal_array.
INPUT:
k – (integer) number of columns. If k=None it is set to the largest value available.
n – (integer) number of symbols
t – (integer; default: 2) – strength of the array
check – (boolean) Whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.
existence (boolean) – instead of building the design, return:
- True – meaning that Sage knows how to build the design
- Unknown – meaning that Sage does not know how to build the design, but that the design may exist (see sage.misc.unknown).
- False – meaning that the design does not exist.
Note
When k=None and existence=True the function returns an
integer, i.e. the largest such that we can build a
.
OUTPUT:
The kind of output depends on the input:
Note
This method implements theorems from [Stinson2004]. See the code’s documentation for details.
See also
When an orthogonal array is also a transversal design (see
transversal_design()) and a family of mutually orthogonal latin
squares (see
mutually_orthogonal_latin_squares()).
EXAMPLES:
sage: designs.orthogonal_array(3,2)
[[0, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]]
sage: designs.orthogonal_array(5,5)
[[0, 0, 0, 0, 0], [0, 1, 2, 3, 4], [0, 2, 4, 1, 3],
[0, 3, 1, 4, 2], [0, 4, 3, 2, 1], [1, 0, 4, 3, 2],
[1, 1, 1, 1, 1], [1, 2, 3, 4, 0], [1, 3, 0, 2, 4],
[1, 4, 2, 0, 3], [2, 0, 3, 1, 4], [2, 1, 0, 4, 3],
[2, 2, 2, 2, 2], [2, 3, 4, 0, 1], [2, 4, 1, 3, 0],
[3, 0, 2, 4, 1], [3, 1, 4, 2, 0], [3, 2, 1, 0, 4],
[3, 3, 3, 3, 3], [3, 4, 0, 1, 2], [4, 0, 1, 2, 3],
[4, 1, 3, 0, 2], [4, 2, 0, 3, 1], [4, 3, 2, 1, 0],
[4, 4, 4, 4, 4]]
What is the largest value of for which Sage knows how to compute a
?:
sage: designs.orthogonal_array(None,14,existence=True)
6
If you ask for an orthogonal array that does not exist, then the function either raise an EmptySetError (if it knows that such an orthogonal array does not exist) or a NotImplementedError:
sage: designs.orthogonal_array(4,2)
Traceback (most recent call last):
...
EmptySetError: No Orthogonal Array exists when k>=n+t except when n<=1
sage: designs.orthogonal_array(12,20)
Traceback (most recent call last):
...
NotImplementedError: I don't know how to build an OA(12,20)!
Note that these errors correspond respectively to the answers False and Unknown when the parameter existence is set to True:
sage: designs.orthogonal_array(4,2,existence=True)
False
sage: designs.orthogonal_array(12,20,existence=True)
Unknown
TESTS:
The special cases :
sage: designs.orthogonal_array(3,0)
[]
sage: designs.orthogonal_array(3,1)
[[0, 0, 0]]
sage: designs.orthogonal_array(None,0,existence=True)
+Infinity
sage: designs.orthogonal_array(None,1,existence=True)
+Infinity
sage: designs.orthogonal_array(None,1)
Traceback (most recent call last):
...
ValueError: there is no upper bound on k when 0<=n<=1
sage: designs.orthogonal_array(None,0)
Traceback (most recent call last):
...
ValueError: there is no upper bound on k when 0<=n<=1
sage: designs.orthogonal_array(16,0)
[]
sage: designs.orthogonal_array(16,1)
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
when and
:
sage: t = 3
sage: designs.orthogonal_array(None,5,t=t,existence=True) == t
True
sage: _ = designs.orthogonal_array(t,5,t)
Return a transversal design of parameters .
A transversal design of parameters is a collection
of
subsets of
(where the groups
are
disjoint and have cardinality
) such that:
More general definitions sometimes involve a parameter, and we
assume here that
.
For more information on transversal designs, see http://mathworld.wolfram.com/TransversalDesign.html.
INPUT:
– integers. If k is None it is set to the largest value
available.
check – (boolean) Whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.
existence (boolean) – instead of building the design, return:
- True – meaning that Sage knows how to build the design
- Unknown – meaning that Sage does not know how to build the design, but that the design may exist (see sage.misc.unknown).
- False – meaning that the design does not exist.
Note
When k=None and existence=True the function returns an
integer, i.e. the largest such that we can build a
.
OUTPUT:
The kind of output depends on the input:
See also
orthogonal_array() – a tranversal design is equivalent to an
orthogonal array
.
EXAMPLES:
sage: designs.transversal_design(5,5)
[[0, 5, 10, 15, 20], [0, 6, 12, 18, 24], [0, 7, 14, 16, 23],
[0, 8, 11, 19, 22], [0, 9, 13, 17, 21], [1, 5, 14, 18, 22],
[1, 6, 11, 16, 21], [1, 7, 13, 19, 20], [1, 8, 10, 17, 24],
[1, 9, 12, 15, 23], [2, 5, 13, 16, 24], [2, 6, 10, 19, 23],
[2, 7, 12, 17, 22], [2, 8, 14, 15, 21], [2, 9, 11, 18, 20],
[3, 5, 12, 19, 21], [3, 6, 14, 17, 20], [3, 7, 11, 15, 24],
[3, 8, 13, 18, 23], [3, 9, 10, 16, 22], [4, 5, 11, 17, 23],
[4, 6, 13, 15, 22], [4, 7, 10, 18, 21], [4, 8, 12, 16, 20],
[4, 9, 14, 19, 24]]
Some examples of the maximal number of transversal Sage is able to build:
sage: TD_4_10 = designs.transversal_design(4,10)
sage: designs.transversal_design(5,10,existence=True)
Unknown
For prime powers, there is an explicit construction which gives a
:
sage: designs.transversal_design(4, 3, existence=True)
True
sage: designs.transversal_design(674, 673, existence=True)
True
For other values of n it depends:
sage: designs.transversal_design(7, 6, existence=True)
False
sage: designs.transversal_design(4, 6, existence=True)
Unknown
sage: designs.transversal_design(3, 6, existence=True)
True
sage: designs.transversal_design(11, 10, existence=True)
False
sage: designs.transversal_design(4, 10, existence=True)
True
sage: designs.transversal_design(5, 10, existence=True)
Unknown
sage: designs.transversal_design(7, 20, existence=True)
Unknown
sage: designs.transversal_design(6, 12, existence=True)
True
sage: designs.transversal_design(7, 12, existence=True)
True
sage: designs.transversal_design(8, 12, existence=True)
Unknown
sage: designs.transversal_design(6, 20, existence = True)
True
sage: designs.transversal_design(7, 20, existence = True)
Unknown
If you ask for a transversal design that Sage is not able to build then an EmptySetError or a NotImplementedError is raised:
sage: designs.transversal_design(47, 100)
Traceback (most recent call last):
...
NotImplementedError: I don't know how to build a TD(47,100)!
sage: designs.transversal_design(55, 54)
Traceback (most recent call last):
...
EmptySetError: There exists no TD(55,54)!
Those two errors correspond respectively to the cases where Sage answer Unknown or False when the parameter existence is set to True:
sage: designs.transversal_design(47, 100, existence=True)
Unknown
sage: designs.transversal_design(55, 54, existence=True)
False
If for a given you want to know the largest
for which Sage is able
to build a
just call the function with
set to None and
existence set to True as follows:
sage: designs.transversal_design(None, 6, existence=True)
3
sage: designs.transversal_design(None, 20, existence=True)
6
sage: designs.transversal_design(None, 30, existence=True)
6
sage: designs.transversal_design(None, 120, existence=True)
9
TESTS:
The case when :
sage: designs.transversal_design(5,1)
[[0, 1, 2, 3, 4]]
Obtained through Wilson’s decomposition:
sage: _ = designs.transversal_design(4,38)
Obtained through product decomposition:
sage: _ = designs.transversal_design(6,60)
sage: _ = designs.transversal_design(5,60) # checks some tricky divisibility error
For small values of the parameter n we check the coherence of the function transversal_design():
sage: for n in xrange(2,25): # long time -- 15 secs
....: i = 2
....: while designs.transversal_design(i, n, existence=True) is True:
....: i += 1
....: _ = designs.transversal_design(i-1, n)
....: assert designs.transversal_design(None, n, existence=True) == i - 1
....: j = i
....: while designs.transversal_design(j, n, existence=True) is Unknown:
....: try:
....: _ = designs.transversal_design(j, n)
....: raise AssertionError("no NotImplementedError")
....: except NotImplementedError:
....: pass
....: j += 1
....: k = j
....: while k < n+4:
....: assert designs.transversal_design(k, n, existence=True) is False
....: try:
....: _ = designs.transversal_design(k, n)
....: raise AssertionError("no EmptySetError")
....: except EmptySetError:
....: pass
....: k += 1
....: print "%2d: (%2d, %2d)"%(n,i,j)
2: ( 4, 4)
3: ( 5, 5)
4: ( 6, 6)
5: ( 7, 7)
6: ( 4, 7)
7: ( 9, 9)
8: (10, 10)
9: (11, 11)
10: ( 5, 11)
11: (13, 13)
12: ( 8, 14)
13: (15, 15)
14: ( 7, 15)
15: ( 7, 17)
16: (18, 18)
17: (19, 19)
18: ( 8, 20)
19: (21, 21)
20: ( 7, 22)
21: ( 8, 22)
22: ( 6, 23)
23: (25, 25)
24: (10, 26)
The special case :
sage: designs.transversal_design(3, 1)
[[0, 1, 2]]
sage: designs.transversal_design(None, 1, existence=True)
+Infinity
sage: designs.transversal_design(None, 1)
Traceback (most recent call last):
...
ValueError: there is no upper bound on k when 0<=n<=1
Return a from a truncated
by Wilson’s construction.
Let be a truncated
with
truncated columns of sizes
, whose blocks have sizes in
. If there
exist:
Then there exists an . The construction is a
generalization of Lemma 3.16 in [HananiBIBD].
INPUT:
REFERENCE:
[HananiBIBD] | Balanced incomplete block designs and related designs, Haim Hanani, Discrete Mathematics 11.3 (1975) pages 255-369. |
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays import wilson_construction
sage: from sage.combinat.designs.orthogonal_arrays import OA_relabel
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_wilson_decomposition_with_one_truncated_group
sage: total = 0
sage: for k in range(3,8):
....: for n in range(1,30):
....: if find_wilson_decomposition_with_one_truncated_group(k,n):
....: total += 1
....: f, args = find_wilson_decomposition_with_one_truncated_group(k,n)
....: _ = f(*args)
sage: print total
41