Orthogonal arrays (find recursive constructions)
This module implements several functions to find recursive constructions of Orthogonal Arrays.
The main function of this module, i.e. find_recursive_construction(),
queries all implemented recursive constructions of designs implemented in
orthogonal_arrays_build_recursive in order to
obtain an .
find_recursive_construction() is called by the orthogonal_array() function.
find_recursive_construction() | Find a recursive construction of an ![]() |
find_product_decomposition() | Find ![]() ![]() |
find_wilson_decomposition_with_one_truncated_group() | Find ![]() ![]() |
find_wilson_decomposition_with_two_truncated_groups() | Find ![]() ![]() |
find_construction_3_3() | Find a decomposition for construction 3.3 from [AC07]. |
find_construction_3_4() | Find a decomposition for construction 3.4 from [AC07]. |
find_construction_3_5() | Find a decomposition for construction 3.5 from [AC07]. |
find_construction_3_6() | Find a decomposition for construction 3.6 from [AC07]. |
find_q_x() | Find integers ![]() ![]() ![]() |
find_thwart_lemma_3_5() | Find the values on which Lemma 3.5 from [Thwarts] applies. |
find_thwart_lemma_4_1() | Find a decomposition for Lemma 4.1 from [Thwarts]. |
find_three_factor_product() | Find ![]() ![]() |
find_brouwer_separable_design() | Find ![]() ![]() |
find_brouwer_van_rees_with_one_truncated_column() | Find ![]() ![]() |
REFERENCES:
[AC07] | (1, 2, 3, 4, 5, 6, 7, 8) Concerning eight mutually orthogonal latin squares Julian R. Abel, Nicholas Cavenagh Journal of Combinatorial Designs Vol. 15, n.3, pp. 255-261 2007 |
Find to obtain an
by Brouwer’s separable design construction.
INPUT:
The assumptions made on the parameters are explained in the
documentation of
brouwer_separable_design().
EXAMPLE:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_brouwer_separable_design
sage: find_brouwer_separable_design(5,13)[1]
(5, 1, 3, 0)
sage: find_brouwer_separable_design(5,14)
False
Find such that the Brouwer-van Rees constructions yields a
.
Let such that
. The
generalization of Wilson’s construction found by Brouwer and van
Rees (with one truncated column) ensures that an
exists
if the following designs exist:
,
,
,
, ...,
.
For more information, see the documentation of wilson_construction().
INPUT:
EXAMPLE:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_brouwer_van_rees_with_one_truncated_column
sage: find_brouwer_van_rees_with_one_truncated_column(5,53)[1]
(None, 5, 7, 7, [[(2, 1), (2, 1)]])
sage: find_brouwer_van_rees_with_one_truncated_column(6,96)[1]
(None, 6, 7, 13, [[(3, 1), (1, 1), (1, 1)]])
Find a decomposition for construction 3.3 from [AC07]
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_construction_3_3
sage: find_construction_3_3(11,177)[1]
(11, 11, 16, 1)
sage: find_construction_3_3(12,11)
Find a decomposition for construction 3.4 from [AC07]
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_construction_3_4
sage: find_construction_3_4(8,196)[1]
(8, 25, 7, 12, 9)
sage: find_construction_3_4(9,24)
Find a decomposition for construction 3.5 from [AC07]
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_construction_3_5
sage: find_construction_3_5(8,111)[1]
(8, 13, 6, 9, 11, 13)
sage: find_construction_3_5(9,24)
Find a decomposition for construction 3.6 from [AC07]
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_construction_3_6
sage: find_construction_3_6(8,95)[1]
(8, 13, 7, 4)
sage: find_construction_3_6(8,98)
Find to obtain an
by the product construction.
If Sage can build a and a
such that
then a
can be built by a product construction (which
correspond to Wilson’s construction with no truncated column). This
function look for a pair of integers
with
,
and such that both an
and an
are
available.
INPUT:
OUTPUT:
A pair f,args such that f(*args) is an or False if no
product decomposition was found.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_product_decomposition
sage: f,args = find_product_decomposition(6, 84)
sage: args
(None, 6, 7, 12, (), False)
sage: _ = f(*args)
Find integers such that the
construction yields an
.
See the documentation of construction_q_x() to find out what
hypotheses the integers must satisfy.
Warning
For efficiency reasons, this function checks that Sage can build an
and an
, which is stronger than checking
that Sage can build a
and a
. The latter would trigger a lot of
independent set computations in
sage.combinat.designs.orthogonal_arrays.incomplete_orthogonal_array().
INPUT:
See also
EXAMPLE:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_q_x
sage: find_q_x(10,9)
False
sage: find_q_x(9,158)[1]
(9, 16, 6)
Find a recursive construction of an (calls all others find_* functions)
This determines whether an can be built through the following
constructions:
INPUT:
OUTPUT:
Return a pair f,args such that f(*args) returns the requested
if possible, and False otherwise.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_recursive_construction
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array
sage: count = 0
sage: for n in range(10,150):
....: k = designs.orthogonal_arrays.largest_available_k(n)
....: if find_recursive_construction(k,n):
....: count = count + 1
....: f,args = find_recursive_construction(k,n)
....: OA = f(*args)
....: assert is_orthogonal_array(OA,k,n,2,verbose=True)
sage: print count
56
Find to obtain an
by the three-factor product from [DukesLing14]
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_three_factor_product
sage: find_three_factor_product(10,648)[1]
(9, 8, 9, 9)
sage: find_three_factor_product(10,50)
False
Find the values on which Lemma 3.5 from [Thwarts] applies.
OUTPUT:
A pair (f,args) such that f(*args) returns an or False
if the construction is not available.
See also
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_thwart_lemma_3_5
sage: from sage.combinat.designs.designs_pyx import is_orthogonal_array
sage: f,args = find_thwart_lemma_3_5(7,66)
sage: args
(7, 9, 7, 1, 1, 1, 0, False)
sage: OA = f(*args)
sage: is_orthogonal_array(OA,7,66,2)
True
sage: f,args = find_thwart_lemma_3_5(6,100)
sage: args
(6, 8, 10, 8, 7, 5, 0, True)
sage: OA = f(*args)
sage: is_orthogonal_array(OA,6,100,2)
True
Some values from [Thwarts]:
sage: kn = ((10,1046), (10,1048), (10,1059), (11,1524),
....: (11,2164), (12,3362), (12,3992), (12,3994))
sage: for k,n in kn:
....: print k,n,find_thwart_lemma_3_5(k,n)[1]
10 1046 (10, 13, 79, 9, 1, 0, 9, False)
10 1048 (10, 13, 79, 9, 1, 0, 11, False)
10 1059 (10, 13, 80, 9, 1, 0, 9, False)
11 1524 (11, 19, 78, 16, 13, 13, 0, True)
11 2164 (11, 27, 78, 23, 19, 16, 0, True)
12 3362 (12, 16, 207, 13, 13, 11, 13, True)
12 3992 (12, 19, 207, 16, 13, 11, 19, True)
12 3994 (12, 19, 207, 16, 13, 13, 19, True)
sage: for k,n in kn: # not tested -- too long
....: assert designs.orthogonal_array(k,n,existence=True) is True # not tested -- too long
Find a decomposition for Lemma 4.1 from [Thwarts].
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_thwart_lemma_4_1
sage: find_thwart_lemma_4_1(10,408)[1]
(10, 13, 28)
sage: find_thwart_lemma_4_1(10,50)
False
Find to obtain an
by Wilson’s construction with one truncated column.
This function looks for possible integers satisfying that
and
such that Sage knows how to build a
,
,
and a
.
INPUT:
OUTPUT:
A pair f,args such that f(*args) is an or False if no
decomposition with one truncated block was found.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_wilson_decomposition_with_one_truncated_group
sage: f,args = find_wilson_decomposition_with_one_truncated_group(4,38)
sage: args
(None, 4, 5, 7, (3,), False)
sage: _ = f(*args)
sage: find_wilson_decomposition_with_one_truncated_group(4,20)
False
Find to obtain an
by Wilson’s construction with two truncated columns.
Look for integers satisfying
and
and such that the following designs exist :
,
,
,
,
,
.
INPUT:
OUTPUT:
A pair f,args such that f(*args) is an or False if no
decomposition with two truncated blocks was found.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_wilson_decomposition_with_two_truncated_groups
sage: f,args = find_wilson_decomposition_with_two_truncated_groups(5,58)
sage: args
(None, 5, 7, 7, (4, 5), False)
sage: _ = f(*args)
Return a tuple of less then
elements of
such
that
. If there is no such tuples then the
function returns None.
INPUT:
EXAMPLE:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import int_as_sum
sage: D = int_as_sum(21,[5,12],100)
sage: for k in range(20,40):
....: print k, int_as_sum(k,[5,12],100)
20 (5, 5, 5, 5)
21 None
22 (12, 5, 5)
23 None
24 (12, 12)
25 (5, 5, 5, 5, 5)
26 None
27 (12, 5, 5, 5)
28 None
29 (12, 12, 5)
30 (5, 5, 5, 5, 5, 5)
31 None
32 (12, 5, 5, 5, 5)
33 None
34 (12, 12, 5, 5)
35 (5, 5, 5, 5, 5, 5, 5)
36 (12, 12, 12)
37 (12, 5, 5, 5, 5, 5)
38 None
39 (12, 12, 5, 5, 5)