Orthogonal arrays (OA)¶
This module gathers some construction related to orthogonal arrays (or
transversal designs). One can build an (or check that it can be built)
from the Sage console with
designs.orthogonal_arrays.build
:
sage: OA = designs.orthogonal_arrays.build(4,8)
See also the modules orthogonal_arrays_build_recursive
or
orthogonal_arrays_find_recursive
for recursive
constructions.
This module 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_n_times_2_pow_c_from_matrix() |
Return an ![]() ![]() |
OA_from_wider_OA() |
Return the first ![]() ![]() |
QDM_from_Vmt() |
Return a QDM a ![]() |
REFERENCES:
[CD96] | Making the MOLS table Charles Colbourn and Jeffrey Dinitz Computational and constructive design theory vol 368,pages 67-134 1996 |
Functions¶
-
class
sage.combinat.designs.orthogonal_arrays.
OAMainFunctions
(*args, **kwds)¶ Functions related to orthogonal arrays.
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.
For more information on orthogonal arrays, see Wikipedia article Orthogonal_array.
From here you have access to:
build(k,n,t=2)
: return an orthogonal array with the given parameters.is_available(k,n,t=2)
: answer whether there is a construction available in Sage for a given set of parameters.exists(k,n,t=2)
: answer whether an orthogonal array with these parameters exist.largest_available_k(n,t=2)
: return the largest integersuch that Sage knows how to build an
.
explain_construction(k,n,t=2)
: return a string that explains the construction that Sage uses to build an.
EXAMPLES:
sage: designs.orthogonal_arrays.build(3,2) [[0, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]] sage: designs.orthogonal_arrays.build(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_arrays.largest_available_k(14) 6
If you ask for an orthogonal array that does not exist, then you will either obtain an
EmptySetError
(if it knows that such an orthogonal array does not exist) or aNotImplementedError
:sage: designs.orthogonal_arrays.build(4,2) Traceback (most recent call last): ... EmptySetError: There exists no OA(4,2) as k(=4)>n+t-1=3 sage: designs.orthogonal_arrays.build(12,20) Traceback (most recent call last): ... NotImplementedError: I don't know how to build an OA(12,20)!
-
static
build
(k, n, t=2, resolvable=False)¶ Return an
of strength
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,n,t
(integers) – parameters of the orthogonal array.resolvable
(boolean) – set toTrue
if you want the design to be resolvable. Theclasses of the resolvable design are obtained as the first
blocks, then the next
blocks, etc ... Set to
False
by default.
EXAMPLES:
sage: designs.orthogonal_arrays.build(3,3,resolvable=True) # indirect doctest [[0, 0, 0], [1, 2, 1], [2, 1, 2], [0, 2, 2], [1, 1, 0], [2, 0, 1], [0, 1, 1], [1, 0, 2], [2, 2, 0]] sage: OA_7_50 = designs.orthogonal_arrays.build(7,50) # indirect doctest
-
static
exists
(k, n, t=2)¶ Return the existence status of an
INPUT:
k,n,t
(integers) – parameters of the orthogonal array.
Warning
The function does not only return booleans, but
True
,False
, orUnknown
.See also
EXAMPLE:
sage: designs.orthogonal_arrays.exists(3,6) # indirect doctest True sage: designs.orthogonal_arrays.exists(4,6) # indirect doctest Unknown sage: designs.orthogonal_arrays.exists(7,6) # indirect doctest False
-
static
explain_construction
(k, n, t=2)¶ Return a string describing how to builds an
INPUT:
k,n,t
(integers) – parameters of the orthogonal array.
EXAMPLE:
sage: designs.orthogonal_arrays.explain_construction(9,565) "Wilson's construction n=23.24+13 with master design OA(9+1,23)" sage: designs.orthogonal_arrays.explain_construction(10,154) 'the database contains a (137,10;1,0;17)-quasi difference matrix'
-
static
is_available
(k, n, t=2)¶ Return whether Sage can build an
.
INPUT:
k,n,t
(integers) – parameters of the orthogonal array.
See also
EXAMPLE:
sage: designs.orthogonal_arrays.is_available(3,6) # indirect doctest True sage: designs.orthogonal_arrays.is_available(4,6) # indirect doctest False
-
static
largest_available_k
(n, t=2)¶ Return the largest
such that Sage can build an
.
INPUT:
n
(integer)t
– (integer; default: 2) – strength of the array
EXAMPLE:
sage: designs.orthogonal_arrays.largest_available_k(0) +Infinity sage: designs.orthogonal_arrays.largest_available_k(1) +Infinity sage: designs.orthogonal_arrays.largest_available_k(10) 4 sage: designs.orthogonal_arrays.largest_available_k(27) 28 sage: designs.orthogonal_arrays.largest_available_k(100) 10 sage: designs.orthogonal_arrays.largest_available_k(-1) Traceback (most recent call last): ... ValueError: n(=-1) was expected to be >=0
-
sage.combinat.designs.orthogonal_arrays.
OA_find_disjoint_blocks
(OA, k, n, x)¶ 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:
OA
– an orthogonal arrayk,n,x
(integers)
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_arrays.build(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_arrays.build(k,n),k,n,5) Traceback (most recent call last): ... ValueError: There does not exist 5 disjoint blocks in this OA(3,4)
-
sage.combinat.designs.orthogonal_arrays.
OA_from_PBD
(k, n, PBD, check=True)¶ 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:
- A
defined over the elements of
for every
.
- The rows
of length
for every
.
Note
This function raises an exception when Sage is unable to build the necessary designs.
INPUT:
k,n
(integers)PBD
– a PBD on.
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
for this PBD (although there exists 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 intersect in a projective plane.
Or an
(as the PBD has 10 points):
sage: _ = OA_from_PBD(3,6,pbd) Traceback (most recent call last): ... RuntimeError: PBD is not a valid Pairwise Balanced Design on [0,...,5]
- A
-
sage.combinat.designs.orthogonal_arrays.
OA_from_Vmt
(m, t, V)¶ Return an Orthogonal Array from a
INPUT:
m,t
(integers)V
– the vector.
EXAMPLES:
sage: _ = designs.orthogonal_arrays.build(6,46) # indirect doctest
-
sage.combinat.designs.orthogonal_arrays.
OA_from_quasi_difference_matrix
(M, G, add_col=True, fill_hole=True)¶ 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 column 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 column contains exactly
entries, and each row 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
rows 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 column. Develop the resulting matrix over the group
(leaving infinite symbols fixed), to obtain a
matrix
. Then
is an orthogonal array with
columns 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:
M
– the difference matrix whose entries belong toG
G
– a groupadd_col
(boolean) – whether to add a column to the final OA equal towhere
.
fill_hole
(boolean) – whether to return the incomplete orthogonal array, or complete it with the(default). When
fill_hole is None
, no block of the incomplete OA contains more than one value.
EXAMPLES:
sage: _ = designs.orthogonal_arrays.build(6,20) # indirect doctest
-
sage.combinat.designs.orthogonal_arrays.
OA_from_wider_OA
(OA, k)¶ Return the first
columns of
.
If
has
columns, this function returns
immediately.
INPUT:
OA
– an orthogonal array.k
(integer)
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays import OA_from_wider_OA sage: OA_from_wider_OA(designs.orthogonal_arrays.build(6,20,2),1)[:5] [(19,), (19,), (19,), (19,), (19,)] sage: _ = designs.orthogonal_arrays.build(5,46) # indirect doctest
-
sage.combinat.designs.orthogonal_arrays.
OA_n_times_2_pow_c_from_matrix
(k, c, G, A, Y, check=True)¶ Return an
from a constrained
-difference matrix.
This construction appears in [AbelCheng1994] and [AbelThesis].
Let
be an additive Abelian group. We denote by
a
-hyperplane in
.
Let
be a
array with entries in
and
be a vector with
entries in
. Let
and
be respectively the part of the array that belong to
and
.
The input
and
must satisfy the following conditions. For any
and
:
- there are exactly two values of
such that
(i.e.
is a
-difference matrix),
- let
and
denote the two values of
given above, then exactly one of
and
belongs to the
-hyperplane
(we implicitely assumed that
).
Under these conditions, it is easy to check that the array whose
rows of length
indexed by
given by
where
is a
-difference matrix.
INPUT:
k,c
(integers) – integersG
– an additive Abelian groupA
– a matrix with entries inY
– a vector with entries incheck
– (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 toTrue
by default.
Note
By convention, a multiplicative generator
of
is fixed (inside the function). The hyperplane
is the one spanned by
. The
part of the input matrix
and vector
are given in the following form: the integer
corresponds to the element
and
None
corresponds to.
See also
Several examples use this construction:
EXAMPLE:
sage: from sage.combinat.designs.orthogonal_arrays import OA_n_times_2_pow_c_from_matrix sage: from sage.combinat.designs.designs_pyx import is_orthogonal_array sage: A = [ ....: [(0,None),(0,None),(0,None),(0,None),(0,None),(0,None),(0,None),(0,None),(0,None),(0,None)], ....: [(0,None),(1,None), (2,2), (3,2), (4,2),(2,None),(3,None),(4,None), (0,2), (1,2)], ....: [(0,None), (2,5), (4,5), (1,2), (3,6), (3,4), (0,0), (2,1), (4,1), (1,6)], ....: [(0,None), (3,4), (1,4), (4,0), (2,5),(3,None), (1,0), (4,1), (2,2), (0,3)], ....: ] sage: Y = [None, 0, 1, 6] sage: OA = OA_n_times_2_pow_c_from_matrix(5,3,GF(5),A,Y) sage: is_orthogonal_array(OA,5,40,2) True sage: A[0][0] = (1,None) sage: OA_n_times_2_pow_c_from_matrix(5,3,GF(5),A,Y) Traceback (most recent call last): ... ValueError: the first part of the matrix A must be a (G,k-1,2)-difference matrix sage: A[0][0] = (0,0) sage: OA_n_times_2_pow_c_from_matrix(5,3,GF(5),A,Y) Traceback (most recent call last): ... ValueError: B_2,0 - B_0,0 = B_2,6 - B_0,6 but the associated part of the matrix C does not satisfies the required condition
REFERENCES:
[AbelThesis] On the Existence of Balanced Incomplete Block Designs and Transversal Designs, Julian R. Abel, PhD Thesis, University of New South Wales, 1995 [AbelCheng1994] R.J.R. Abel and Y.W. Cheng, Some new MOLS of order 2np for p a prime power, The Australasian Journal of Combinatorics, vol 10 (1994) - there are exactly two values of
-
sage.combinat.designs.orthogonal_arrays.
OA_relabel
(OA, k, n, blocks=(), matrix=None)¶ 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 frominto
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 dimensionssuch that if the i th coordinate of a block is
, this
will be relabelled with
matrix[i][x]
. This is not necessarily an integer betweenand
, 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 aNone
coordinate in the final block.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays import OA_relabel sage: OA = designs.orthogonal_arrays.build(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_arrays.build(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_arrays.build(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_arrays.build(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
-
sage.combinat.designs.orthogonal_arrays.
QDM_from_Vmt
(m, t, V)¶ Return a QDM 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 row of length
whose first entry is empty, and whose remaining entries are
. Form
rows by multiplying this row by the
th roots, i.e. the powers of
. From each of these
rows, form
rows by taking the
cyclic shifts of the row. The result is a
.
For more information, refer to the Handbook of Combinatorial Designs [DesignHandbook].
INPUT:
m,t
(integers)V
– the vector.
See also
EXAMPLES:
sage: _ = designs.orthogonal_arrays.build(6,46) # indirect doctest
-
sage.combinat.designs.orthogonal_arrays.
TD_product
(k, TD1, n1, TD2, n2, check=True)¶ 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:
TD1, TD2
– transversal designs.k,n1,n2
(integers) – see above.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 toTrue
by default.
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)
-
class
sage.combinat.designs.orthogonal_arrays.
TransversalDesign
(blocks, k=None, n=None, check=True, **kwds)¶ Bases:
sage.combinat.designs.group_divisible_designs.GroupDivisibleDesign
Class for Transversal Designs
INPUT:
blocks
– collection of blocksk,n
(integers) – parameters of the transversal design. They can be set toNone
(default) in which case their value is determined by the blocks.check
(boolean) – whether to check that the design is indeed a transversal design with the right parameters. Set toTrue
by default.
EXAMPLES:
sage: designs.transversal_design(None,5) Transversal Design TD(6,5) sage: designs.transversal_design(None,30) Transversal Design TD(6,30) sage: designs.transversal_design(None,36) Transversal Design TD(10,36)
-
sage.combinat.designs.orthogonal_arrays.
incomplete_orthogonal_array
(k, n, holes, resolvable=False, existence=False)¶ Return an
.
An
is an orthogonal array from which have been removed disjoint
. If there exist
they can be used to fill the holes and give rise to an
.
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.
INPUT:
k,n
(integers)holes
(list of integers) – respective sizes of the holes to be found.resolvable
(boolean) – set toTrue
if you want the design to be resolvable. The classes of the resolvable design are obtained as the firstblocks, then the next
blocks, etc ... Set to
False
by default.existence
(boolean) – instead of building the design, return:True
– meaning that Sage knows how to build the designUnknown
– meaning that Sage does not know how to build the design, but that the design may exist (seesage.misc.unknown
).False
– meaning that the design does not exist.
Note
By convention, the ground set is always
.
If all holes have size 1, in the incomplete orthogonal array returned by this function the holes are
,
, etc.
More generally, if
holes
is equal to, the
-th hole is the set of points
.
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 intersect in a projective plane. sage: n=10 sage: k=designs.orthogonal_arrays.largest_available_k(n) 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])
A resolvable
. We check that extending each class and adding the
blocks turns it into an
.:
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array sage: k,n=5,7 sage: OA = designs.incomplete_orthogonal_array(k,n,[1]*n,resolvable=True) sage: classes = [OA[i*n:(i+1)*n] for i in range(n-1)] sage: for classs in classes: # The design is resolvable ! ....: assert(len(set(col))==n for col in zip(*classs)) sage: OA.extend([[i]*(k) for i in range(n)]) sage: for i,R in enumerate(OA): ....: R.append(i//n) sage: is_orthogonal_array(OA,k+1,n) True
Non-existent resolvable incomplete OA:
sage: designs.incomplete_orthogonal_array(9,13,[1]*10,resolvable=True,existence=True) False sage: designs.incomplete_orthogonal_array(9,13,[1]*10,resolvable=True) Traceback (most recent call last): ... EmptySetError: There is no resolvable incomplete OA(9,13) whose holes' sizes sum to 10<n(=13)
Error message for big holes:
sage: designs.incomplete_orthogonal_array(6,4*9,[9,9,8]) Traceback (most recent call last): ... NotImplementedError: I was not able to build this OA(6,36)-OA(6,8)-2.OA(6,9)
10 holes of size 9 through the product construction:
sage: iOA = designs.incomplete_orthogonal_array(10,153,[9]*10) # long time sage: OA9 = designs.orthogonal_arrays.build(10,9) # long time sage: for i in range(10): # long time ....: iOA.extend([[153-9*(i+1)+x for x in B] for B in OA9]) # long time sage: is_orthogonal_array(iOA,10,153) # long time True
An
:
sage: ioa = designs.incomplete_orthogonal_array(9,82,[9,1]) sage: ioa.extend([[x+72 for x in B] for B in designs.orthogonal_arrays.build(9,9)]) sage: ioa.extend([[x+81 for x in B] for B in designs.orthogonal_arrays.build(9,1)]) sage: is_orthogonal_array(ioa,9,82,verbose=1) True
An
in different orders:
sage: ioa = designs.incomplete_orthogonal_array(9,82,[1,9,1]) sage: ioa.extend([[x+71 for x in B] for B in designs.orthogonal_arrays.build(9,1)]) sage: ioa.extend([[x+72 for x in B] for B in designs.orthogonal_arrays.build(9,9)]) sage: ioa.extend([[x+81 for x in B] for B in designs.orthogonal_arrays.build(9,1)]) sage: is_orthogonal_array(ioa,9,82,verbose=1) True sage: ioa = designs.incomplete_orthogonal_array(9,82,[9,1,1]) sage: ioa.extend([[x+71 for x in B] for B in designs.orthogonal_arrays.build(9,9)]) sage: ioa.extend([[x+80 for x in B] for B in designs.orthogonal_arrays.build(9,1)]) sage: ioa.extend([[x+81 for x in B] for B in designs.orthogonal_arrays.build(9,1)]) sage: is_orthogonal_array(ioa,9,82,verbose=1) True
Three holes of size 1:
sage: ioa = designs.incomplete_orthogonal_array(3,6,[1,1,1]) sage: ioa.extend([[i]*3 for i in [3,4,5]]) sage: is_orthogonal_array(ioa,3,6,verbose=1) True
REFERENCES:
[BvR82] More mutually orthogonal Latin squares, Andries Brouwer and John van Rees Discrete Mathematics vol.39, num.3, pages 263-281 1982 http://oai.cwi.nl/oai/asset/304/0304A.pdf
-
sage.combinat.designs.orthogonal_arrays.
is_transversal_design
(B, k, n, verbose=False)¶ Check that a given set of blocks
B
is a transversal design.See
transversal_design()
for a definition.INPUT:
B
– the list of blocksk, n
– integersverbose
(boolean) – whether to display information about what is going wrong.
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
-
sage.combinat.designs.orthogonal_arrays.
largest_available_k
(n, t=2)¶ Return the largest
such that Sage can build an
.
INPUT:
n
(integer)t
– (integer; default: 2) – strength of the array
EXAMPLE:
sage: designs.orthogonal_arrays.largest_available_k(0) +Infinity sage: designs.orthogonal_arrays.largest_available_k(1) +Infinity sage: designs.orthogonal_arrays.largest_available_k(10) 4 sage: designs.orthogonal_arrays.largest_available_k(27) 28 sage: designs.orthogonal_arrays.largest_available_k(100) 10 sage: designs.orthogonal_arrays.largest_available_k(-1) Traceback (most recent call last): ... ValueError: n(=-1) was expected to be >=0
-
sage.combinat.designs.orthogonal_arrays.
orthogonal_array
(k, n, t=2, resolvable=False, check=True, existence=False, explain_construction=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
.
An orthogonal array is said to be resolvable if it corresponds to a resolvable transversal design (see
sage.combinat.designs.incidence_structures.IncidenceStructure.is_resolvable()
).For more information on orthogonal arrays, see Wikipedia article Orthogonal_array.
INPUT:
k
– (integer) number of columns. Ifk=None
it is set to the largest value available.n
– (integer) number of symbolst
– (integer; default: 2) – strength of the arrayresolvable
(boolean) – set toTrue
if you want the design to be resolvable. Theclasses of the resolvable design are obtained as the first
blocks, then the next
blocks, etc ... Set to
False
by default.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 toTrue
by default.existence
(boolean) – instead of building the design, return:True
– meaning that Sage knows how to build the designUnknown
– meaning that Sage does not know how to build the design, but that the design may exist (seesage.misc.unknown
).False
– meaning that the design does not exist.
Note
When
k=None
andexistence=True
the function returns an integer, i.e. the largestsuch that we can build a
.
explain_construction
(boolean) – return a string describing the construction.
OUTPUT:
The kind of output depends on the input:
- if
existence=False
(the default) then the output is a list of lists that represent an orthogonal array with parametersk
andn
- if
existence=True
andk
is an integer, then the function returns a troolean: eitherTrue
,Unknown
orFalse
- if
existence=True
andk=None
then the output is the largest value ofk
for which Sage knows how to compute a.
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 (seemutually_orthogonal_latin_squares()
).TESTS:
The special cases
:
sage: designs.orthogonal_arrays.build(3,0) [] sage: designs.orthogonal_arrays.build(3,1) [[0, 0, 0]] sage: designs.orthogonal_arrays.largest_available_k(0) +Infinity sage: designs.orthogonal_arrays.largest_available_k(1) +Infinity sage: designs.orthogonal_arrays.build(16,0) [] sage: designs.orthogonal_arrays.build(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_arrays.largest_available_k(5,t=t) == t True sage: _ = designs.orthogonal_arrays.build(t,5,t)
-
sage.combinat.designs.orthogonal_arrays.
transversal_design
(k, n, resolvable=False, check=True, existence=False)¶ 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:
- Any
has cardinality
and intersects each group on exactly one element.
- Any two elements from distincts groups are contained in exactly one
element of
.
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.resolvable
(boolean) – set toTrue
if you want the design to be resolvable (seesage.combinat.designs.incidence_structures.IncidenceStructure.is_resolvable()
). Theclasses of the resolvable design are obtained as the first
blocks, then the next
blocks, etc ... Set to
False
by default.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 toTrue
by default.existence
(boolean) – instead of building the design, return:True
– meaning that Sage knows how to build the designUnknown
– meaning that Sage does not know how to build the design, but that the design may exist (seesage.misc.unknown
).False
– meaning that the design does not exist.
Note
When
k=None
andexistence=True
the function returns an integer, i.e. the largestsuch that we can build a
.
OUTPUT:
The kind of output depends on the input:
- if
existence=False
(the default) then the output is a list of lists that represent awith
- if
existence=True
andk
is an integer, then the function returns a troolean: eitherTrue
,Unknown
orFalse
- if
existence=True
andk=None
then the output is the largest value ofk
for which Sage knows how to compute a.
See also
orthogonal_array()
– a tranversal designis equivalent to an orthogonal array
.
EXAMPLES:
sage: TD = designs.transversal_design(5,5); TD Transversal Design TD(5,5) sage: TD.blocks() [[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 aNotImplementedError
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
orFalse
when the parameterexistence
is set toTrue
: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
andexistence
set toTrue
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).blocks() [[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 functiontransversal_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).blocks() [[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
Resolvable TD:
sage: k,n = 5,15 sage: TD = designs.transversal_design(k,n,resolvable=True) sage: TD.is_resolvable() True sage: r = designs.transversal_design(None,n,resolvable=True,existence=True) sage: non_r = designs.transversal_design(None,n,existence=True) sage: r + 1 == non_r True
- Any
-
sage.combinat.designs.orthogonal_arrays.
wilson_construction
(OA, k, r, m, u, check=True, explain_construction=False)¶ Returns a
from a truncated
by Wilson’s construction.
Simple form:
Let
be a truncated
with
truncated columns of sizes
, whose blocks have sizes in
. If there exist:
- An
for every
- An
for every
Then there exists an
. The construction is a generalization of Lemma 3.16 in [HananiBIBD].
Brouwer-Van Rees form:
Let
be a truncated
with
truncated columns of sizes
. Let the set
of the
points of column
be partitionned into
. Let
be integers such that:
- For
there exists an
- For any block
intersecting the sets
there exists an
.
Then there exists an
. This construction appears in [BvR82].
INPUT:
OA
– an incomplete orthogonal array withcolumns. The elements of a column of size
must belong to
. The missing entries of a block are represented by
None
values. IfOA=None
, it is defined as a truncated orthogonal arrays withcolumns.
k,r,m
(integers)u
(list) – two cases depending on the form to use:- Simple form: a list of length
such that column
k+i
has sizeu[i]
. The untruncated points of columnk+i
are assumed to be[0,...,u[i]-1]
. - Brouwer-Van Rees form: a list of length
such that
u[i]
is the list of pairs. The untruncated points of column
k+i
are assumed to bewhere
. Besides, the first
points represent
, the next
points represent
, etc...
- Simple form: a list of length
explain_construction
(boolean) – return a string describing the construction.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 toTrue
by default.
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_find_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 sage: print designs.orthogonal_arrays.explain_construction(7,58) Wilson's construction n=8.7+1+1 with master design OA(7+2,8) sage: print designs.orthogonal_arrays.explain_construction(9,115) Wilson's construction n=13.8+11 with master design OA(9+1,13) sage: print wilson_construction(None,5,11,21,[[(5,5)]],explain_construction=True) Brouwer-van Rees construction n=11.21+(5.5) with master design OA(5+1,11) sage: print wilson_construction(None,71,17,21,[[(4,9),(1,1)],[(9,9),(1,1)]],explain_construction=True) Brouwer-van Rees construction n=17.21+(9.4+1.1)+(9.9+1.1) with master design OA(71+2,17)
An example using the Brouwer-van Rees generalization:
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array sage: from sage.combinat.designs.orthogonal_arrays import wilson_construction sage: OA = designs.orthogonal_arrays.build(6,11) sage: OA = [[x if (i<5 or x<5) else None for i,x in enumerate(R)] for R in OA] sage: OAb = wilson_construction(OA,5,11,21,[[(5,5)]]) sage: is_orthogonal_array(OAb,5,256) True
- An