Chung, Diaconis and Graham posed the problem to give a necessary and sufficient condition of the existence of -perfect arrays.
As Fan, Fan and Siu proved in 1985, the conditions (2) and (3) are sufficient for the existence of (2,2,a,b)-perfect arrays. Paterson proved the same in 1994 [ 201 ] for -perfect arrays. Later Paterson [ 202 ], [ 203 ] supplied further sufficient conditions.
Hurlbert and Isaak in 1993 gave a construction for one and two dimensional growing arrays.
The following implementation of
was proposed by Iványi and Tóth in 1988. The input of
is the alphabet size and an even sequence w. The output is an -perfect array. It uses the following meshing function [
IFis even 4 5
is an extension and combination of the known algorithms
Shift, Optimal-Martin, Even
results a cellular perfect array . Its input data are and , its output is an -perfect array, where and for .
consists of six parts:
Calculation (line 1 in the pseudocode): determines the new alphabet size using formula (29.2);
Walking (lines 2–3): if , then construction of a perfect symmetric sequence using algorithm
(walking in a De Bruijn graph);
Meshing (lines 4–6): if is even and , then first construct an -ary even perfect sequence using Even, then construct an sized -ary square using meshing function (29.5);
Shifting (lines 7–12): if and ( is odd or ), then use
once, then use
times, receiving a perfect array ;
Combination (lines 13–16): if is even and , then construct an even sequence with
, construct a perfect square by
and finally use of
times, results a perfect array .
Report (line 17): returns the output .
IFand and is even 6
IFis odd or 9
29.4-1 Construct a -perfect array (a binary double square for window size .