This module gathers anything related to orthogonal arrays, and, incidentally, to transversal designs.
Returns a \(TD(6,12)\) as build in [Hanani75].
This design is Lemma 3.21 from [Hanani75].
EXAMPLE:
sage: from sage.combinat.designs.orthogonal_arrays import TD6_12
sage: _ = TD6_12()
REFERENCES:
[Hanani75] | (1, 2) Haim Hanani, Balanced incomplete block designs and related designs, http://dx.doi.org/10.1016/0012-365X(75)90040-0, Discrete Mathematics, Volume 11, Issue 3, 1975, Pages 255-369. |
Check that the integer matrix \(M\) is an \(OA(k,n,t)\).
See orthogonal_array() for a definition.
INPUT:
EXAMPLES:
sage: OA = designs.orthogonal_array(5,9,check=True) # indirect doctest
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array
sage: is_orthogonal_array(OA, 5, 9, 2)
True
sage: is_orthogonal_array(OA, 4, 5, 2)
False
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 \(\{0, \ldots, kn-1\}\) as a ground set, partitioned as \(k\) sets of size \(n\): \(\{0, \ldots, k-1\} \sqcup \{k, \ldots, 2k-1\} \sqcup \cdots \sqcup \{k(n-1), \ldots, kn-1\}\).
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 \(k,n,t\).
An orthogonal array of parameters \(k,n,t\) is a matrix with \(k\) columns filled with integers from \([n]\) in such a way that for any \(t\) columns, each of the \(n^t\) possible rows occurs exactly once. In particular, the matrix has \(n^t\) rows.
More general definitions sometimes involve a \(\lambda\) parameter, and we assume here that \(\lambda=1\).
For more information on orthogonal arrays, see Wikipedia article Orthogonal_array.
INPUT:
Note
This method implements theorems from [Stinson2004]. See the code’s documentation for details.
Todo
Implement Wilson’s construction. See page 146 of [Stinson2004].
See also
transversal_design() – when \(t=2\) an orthogonal array is also called a transversal design.
EXAMPLES:
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, 1, 1, 1, 1], [1, 2, 3, 4, 0], [1, 3, 0, 2, 4],
[1, 4, 2, 0, 3], [1, 0, 4, 3, 2], [2, 2, 2, 2, 2], [2, 3, 4, 0, 1],
[2, 4, 1, 3, 0], [2, 0, 3, 1, 4], [2, 1, 0, 4, 3], [3, 3, 3, 3, 3],
[3, 4, 0, 1, 2], [3, 0, 2, 4, 1], [3, 1, 4, 2, 0], [3, 2, 1, 0, 4],
[4, 4, 4, 4, 4], [4, 0, 1, 2, 3], [4, 1, 3, 0, 2], [4, 2, 0, 3, 1],
[4, 3, 2, 1, 0]]
TESTS:
sage: designs.orthogonal_array(3,2)
[[0, 1, 0], [0, 0, 1], [1, 0, 0], [1, 1, 1]]
sage: designs.orthogonal_array(4,2)
Traceback (most recent call last):
...
EmptySetError: No Orthogonal Array exists when k>=n+t
Return a transversal design of parameters \(k,n\).
A transversal design of parameters \(k, n\) is a collection \(\mathcal{S}\) of subsets of \(V = V_1 \cup \cdots \cup V_k\) (where the groups \(V_i\) are disjoint and have cardinality \(n\)) such that:
More general definitions sometimes involve a \(\lambda\) parameter, and we assume here that \(\lambda=1\).
For more information on transversal designs, see http://mathworld.wolfram.com/TransversalDesign.html.
INPUT:
Note
This function returns transversal designs with \(V_1=\{0,\dots,n-1\},\dots,V_k=\{(k-1)n,\dots,kn-1\}\).
See also
orthogonal_array() – a tranversal design is an orthogonal array with \(t=2\).
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, 6, 11, 16, 21],
[1, 7, 13, 19, 20], [1, 8, 10, 17, 24], [1, 9, 12, 15, 23],
[1, 5, 14, 18, 22], [2, 7, 12, 17, 22], [2, 8, 14, 15, 21],
[2, 9, 11, 18, 20], [2, 5, 13, 16, 24], [2, 6, 10, 19, 23],
[3, 8, 13, 18, 23], [3, 9, 10, 16, 22], [3, 5, 12, 19, 21],
[3, 6, 14, 17, 20], [3, 7, 11, 15, 24], [4, 9, 14, 19, 24],
[4, 5, 11, 17, 23], [4, 6, 13, 15, 22], [4, 7, 10, 18, 21],
[4, 8, 12, 16, 20]]