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_* functions) |
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 |
Functions¶
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_brouwer_separable_design
(k, n)¶ Find
to obtain an
by Brouwer’s separable design construction.
INPUT:
k,n
(integers)
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
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_brouwer_van_rees_with_one_truncated_column
(k, n)¶ 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:
k,n
(integers)
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)]])
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_construction_3_3
(k, n)¶ Find a decomposition for construction 3.3 from [AC07]
INPUT:
k,n
(integers)
See also
OUTPUT:
A pair
f,args
such thatf(*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)
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_construction_3_4
(k, n)¶ Find a decomposition for construction 3.4 from [AC07]
INPUT:
k,n
(integers)
See also
OUTPUT:
A pair
f,args
such thatf(*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)
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_construction_3_5
(k, n)¶ Find a decomposition for construction 3.5 from [AC07]
INPUT:
k,n
(integers)
See also
OUTPUT:
A pair
f,args
such thatf(*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)
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_construction_3_6
(k, n)¶ Find a decomposition for construction 3.6 from [AC07]
INPUT:
k,n
(integers)
See also
OUTPUT:
A pair
f,args
such thatf(*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)
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_product_decomposition
(k, n)¶ 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:
k,n
(integers) – see above.
OUTPUT:
A pair
f,args
such thatf(*args)
is anor
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)
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_q_x
(k, n)¶ Find integers
such that the
construction yields an
.
See the documentation of
construction_q_x()
to find out what hypotheses the integersmust 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:
k,n
(integers)
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)
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_recursive_construction
(k, n)¶ Find a recursive construction of an
(calls all others
find_*
functions)This determines whether an
can be built through the following constructions:
wilson_construction()
construction_3_3()
construction_3_4()
construction_3_5()
construction_3_6()
construction_q_x()
thwart_lemma_3_5()
thwart_lemma_4_1()
three_factor_product()
brouwer_separable_design()
INPUT:
k,n
(integers)
OUTPUT:
Return a pair
f,args
such thatf(*args)
returns the requestedif 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
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_three_factor_product
(k, n)¶ Find
to obtain an
by the three-factor product from [DukesLing14]
INPUT:
k,n
(integers)
See also
OUTPUT:
A pair
f,args
such thatf(*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
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_thwart_lemma_3_5
(k, N)¶ Find the values on which Lemma 3.5 from [Thwarts] applies.
OUTPUT:
A pair
(f,args)
such thatf(*args)
returns anor
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
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_thwart_lemma_4_1
(k, n)¶ Find a decomposition for Lemma 4.1 from [Thwarts].
INPUT:
k,n
(integers)
See also
OUTPUT:
A pair
f,args
such thatf(*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
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_wilson_decomposition_with_one_truncated_group
(k, n)¶ 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:
k,n
(integers) – see above
OUTPUT:
A pair
f,args
such thatf(*args)
is anor
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
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
find_wilson_decomposition_with_two_truncated_groups
(k, n)¶ 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:
k,n
(integers) – see above
OUTPUT:
A pair
f,args
such thatf(*args)
is anor
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)
-
sage.combinat.designs.orthogonal_arrays_find_recursive.
int_as_sum
(value, S, k_max)¶ Return a tuple
of less then
elements of
such that
. If there is no such tuples then the function returns
None
.INPUT:
value
(integer)S
– a list of integersk_max
(integer)
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)