Covering arrays

A covering array, denoted $CA(N;t,k,v)$, is an $N$ by $k$ array with entries from a set of $v$ elements with the property that in every selection of $t$ columns, every sequence of $t$ elements appears in at least one row.

An orthogonal array, denoted $OA(N;t,k,v)$ is a covering array with the property that every sequence of $t$-elements appears in exactly one row. (See sage.combinat.designs.orthogonal_arrays).

This module collects methods relating to covering arrays, some of which are inherited from orthogonal array methods. This module defines the following functions:

is_covering_array()	Check that an input list of lists is a $CA(N;t,k,v)$.
CA_relabel()	Return a relabelled version of the $CA$.
CA_standard_label()	Return a version of the $CA$ relabelled to symbols $(0,\dots ,n-1)$.
truncate_columns()	Return an array with $k$ columns from a larger one.
Kleitman_Spencer_Katona()	Return a $CA(N;2,k,2)$ using N as input.
column_Kleitman_Spencer_Katona()	Return a $CA(N;2,k,2)$ using k as input.
database_check()	Check if CA can be made from the database of combinatorial designs.
covering_array()	Return a $CA$ with given parameters.

REFERENCES:

• [Colb2004]

• [SMC2006]

• [WC2007]

AUTHORS:

• Aaron Dwyer and brett stevens (2022): initial version

sage.combinat.designs.covering_array.Kleitman_Spencer_Katona(N)

Return a $CA(N;2,k,2)$ where $k=(\genfrac{}{}{0ex}{}{N-1}{\lceil N/2\rceil })$.

INPUT:

• N – the number of rows in the array, must be an integer greater than 3 since any smaller would not produce enough columns for a strength 2 array.

This construction is referenced in [Colb2004] from [KS1973] and [Kat1973]

Construction

Take all distinct binary $N$-tuples of weight $N/2$ that have a 0 in the first position and place them as columns in an array.

EXAMPLES:

Sage

sage: from sage.combinat.designs.covering_array import Kleitman_Spencer_Katona
sage: from sage.combinat.designs.designs_pyx import is_covering_array
sage: C = Kleitman_Spencer_Katona(2)
Traceback (most recent call last):
...
ValueError: N must be greater than 3
sage: C = Kleitman_Spencer_Katona(5)
sage: is_covering_array(C,parameters=True)
(True, (5, 2, 4, 2))

Python

>>> from sage.all import *
>>> from sage.combinat.designs.covering_array import Kleitman_Spencer_Katona
>>> from sage.combinat.designs.designs_pyx import is_covering_array
>>> C = Kleitman_Spencer_Katona(Integer(2))
Traceback (most recent call last):
...
ValueError: N must be greater than 3
>>> C = Kleitman_Spencer_Katona(Integer(5))
>>> is_covering_array(C,parameters=True)
(True, (5, 2, 4, 2))

Sage Live

from sage.combinat.designs.covering_array import Kleitman_Spencer_Katona
from sage.combinat.designs.designs_pyx import is_covering_array
C = Kleitman_Spencer_Katona(2)
C = Kleitman_Spencer_Katona(5)
is_covering_array(C,parameters=True)

sage.combinat.designs.covering_array.column_Kleitman_Spencer_Katona(k)

Return a covering array with $k$ columns using the Kleitman-Spencer-Katona method.

See Kleitman_Spencer_Katona()

INPUT:

• k – the number of columns in the array, must be an integer greater than 3 since any smaller is a trivial array for strength 2.

EXAMPLES:

Sage

sage: from sage.combinat.designs.designs_pyx import is_covering_array
sage: from sage.combinat.designs.covering_array import column_Kleitman_Spencer_Katona
sage: C = column_Kleitman_Spencer_Katona(20)
sage: is_covering_array(C,parameters=True)
(True, (8, 2, 20, 2))
sage: column_Kleitman_Spencer_Katona(25000)
Traceback (most recent call last):
...
NotImplementedError: not implemented for k > 24310

Python

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_covering_array
>>> from sage.combinat.designs.covering_array import column_Kleitman_Spencer_Katona
>>> C = column_Kleitman_Spencer_Katona(Integer(20))
>>> is_covering_array(C,parameters=True)
(True, (8, 2, 20, 2))
>>> column_Kleitman_Spencer_Katona(Integer(25000))
Traceback (most recent call last):
...
NotImplementedError: not implemented for k > 24310

Sage Live

from sage.combinat.designs.designs_pyx import is_covering_array
from sage.combinat.designs.covering_array import column_Kleitman_Spencer_Katona
C = column_Kleitman_Spencer_Katona(20)
is_covering_array(C,parameters=True)
column_Kleitman_Spencer_Katona(25000)

sage.combinat.designs.covering_array.covering_array(strength, number_columns, levels)

Build a $CA(N;t,k,v)$ using direct constructions, where $N$ is the smallest size known.

INPUT:

• strength (integer) – the parameter $t$ of the covering array, such that in any selection of $t$ columns of the array, every $t$-tuple appears at least once.

• levels (integer) – the parameter $v$ which is the number of unique symbols that appear in the covering array.

• number_columns (integer) – the number of columns desired for the covering array.

EXAMPLES:

Sage

sage: from sage.combinat.designs.designs_pyx import is_covering_array
sage: from sage.combinat.designs.covering_array import covering_array
sage: C1 = covering_array(2, 7, 3)
sage: is_covering_array(C1,parameters=True)
(True, (12, 2, 7, 3))
sage: C2 = covering_array(2, 11, 2)
sage: is_covering_array(C2,parameters=True)
(True, (7, 2, 11, 2))
sage: C3 = covering_array(2, 8, 7)
sage: is_covering_array(C3,parameters=True)
(True, (49, 2, 8, 7))
sage: C4 = covering_array(2, 50, 7)
No direct construction known and/or implemented for a CA(N; 2, 50, 7)

Python

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_covering_array
>>> from sage.combinat.designs.covering_array import covering_array
>>> C1 = covering_array(Integer(2), Integer(7), Integer(3))
>>> is_covering_array(C1,parameters=True)
(True, (12, 2, 7, 3))
>>> C2 = covering_array(Integer(2), Integer(11), Integer(2))
>>> is_covering_array(C2,parameters=True)
(True, (7, 2, 11, 2))
>>> C3 = covering_array(Integer(2), Integer(8), Integer(7))
>>> is_covering_array(C3,parameters=True)
(True, (49, 2, 8, 7))
>>> C4 = covering_array(Integer(2), Integer(50), Integer(7))
No direct construction known and/or implemented for a CA(N; 2, 50, 7)

Sage Live

from sage.combinat.designs.designs_pyx import is_covering_array
from sage.combinat.designs.covering_array import covering_array
C1 = covering_array(2, 7, 3)
is_covering_array(C1,parameters=True)
C2 = covering_array(2, 11, 2)
is_covering_array(C2,parameters=True)
C3 = covering_array(2, 8, 7)
is_covering_array(C3,parameters=True)
C4 = covering_array(2, 50, 7)

sage.combinat.designs.covering_array.database_check(number_columns, strength, levels)

Check if the database can be used to build a CA with the given parameters. If so return the CA, if not return False.

INPUT:

• strength (integer) – the parameter $t$ of the covering array, such that in any selection of $t$ columns of the array, every $t$-tuple appears at least once.

• levels (integer) – the parameter $v$ which is the number of unique symbols that appear in the covering array.

• number_columns (integer) – the number of columns desired for the covering array.

EXAMPLES:

Sage

sage: from sage.combinat.designs.designs_pyx import is_covering_array
sage: from sage.combinat.designs.covering_array import database_check
sage: C = database_check(6, 2, 3)
sage: is_covering_array(C, parameters=True)
(True, (12, 2, 6, 3))
sage: database_check(6, 3, 3)
False

Python

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_covering_array
>>> from sage.combinat.designs.covering_array import database_check
>>> C = database_check(Integer(6), Integer(2), Integer(3))
>>> is_covering_array(C, parameters=True)
(True, (12, 2, 6, 3))
>>> database_check(Integer(6), Integer(3), Integer(3))
False

Sage Live

from sage.combinat.designs.designs_pyx import is_covering_array
from sage.combinat.designs.covering_array import database_check
C = database_check(6, 2, 3)
is_covering_array(C, parameters=True)
database_check(6, 3, 3)

sage.combinat.designs.covering_array.truncate_columns(array, k)

Return a covering array with $k$ columns, obtained by removing excess columns from a larger covering array.

INPUT:

• array – the array to be truncated.

• k – the number of columns desired. Must be less than the number of columns in array.

EXAMPLES:

Sage

sage: from sage.combinat.designs.designs_pyx import is_covering_array
sage: from sage.combinat.designs.covering_array import truncate_columns
sage: from sage.combinat.designs.database import ca_11_2_5_3
sage: C = ca_11_2_5_3()
sage: D = truncate_columns(C,7)
Traceback (most recent call last):
...
ValueError: array only has 5 columns
sage: E = truncate_columns(C,4)
sage: is_covering_array(E,parameters=True)
(True, (11, 2, 4, 3))

Python

>>> from sage.all import *
>>> from sage.combinat.designs.designs_pyx import is_covering_array
>>> from sage.combinat.designs.covering_array import truncate_columns
>>> from sage.combinat.designs.database import ca_11_2_5_3
>>> C = ca_11_2_5_3()
>>> D = truncate_columns(C,Integer(7))
Traceback (most recent call last):
...
ValueError: array only has 5 columns
>>> E = truncate_columns(C,Integer(4))
>>> is_covering_array(E,parameters=True)
(True, (11, 2, 4, 3))

Sage Live

from sage.combinat.designs.designs_pyx import is_covering_array
from sage.combinat.designs.covering_array import truncate_columns
from sage.combinat.designs.database import ca_11_2_5_3
C = ca_11_2_5_3()
D = truncate_columns(C,7)
E = truncate_columns(C,4)
is_covering_array(E,parameters=True)

Make live