## 29.4. 29.4 Two-dimensional perfect arrays

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 [] for -perfect arrays. Later Paterson [], [] supplied further sufficient conditions.

Hurlbert and Isaak in 1993 gave a construction for one and two dimensional growing arrays.

### 29.4.1. 29.4.1 Pseudocode of the algorithm Mesh

The following implementation of Mesh was proposed by Iványi and Tóth in 1988. The input of Mesh is the alphabet size and an even sequence w. The output is an -perfect array. It uses the following meshing function []: Mesh( )

  1
FOR TO 2
FOR TO 3
IF is even   4 5
ELSE 6
RETURN ### 29.4.2. 29.4.2 Pseudocode of the algorithm Cellular

Algorithm Cellular is an extension and combination of the known algorithms Shift, Optimal-Martin, Even and Mesh .

Cellular results a cellular perfect array . Its input data are and , its output is an -perfect array, where and for . Cellular consists of six parts:

1. Calculation (line 1 in the pseudocode): determines the new alphabet size using formula (29.2);

2. Walking (lines 2–3): if , then construction of a perfect symmetric sequence using algorithm Optimal-Martin (walking in a De Bruijn graph);

3. 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);

4. Shifting (lines 7–12): if and ( is odd or ), then use Martin once, then use Shift times, receiving a perfect array ;

5. Combination (lines 13–16): if is even and , then construct an even sequence with Even , construct a perfect square by Mesh and finally use of Shift times, results a perfect array .

6. Report (line 17): returns the output .

Cellular( )

  1 2
IF 3
Optimal-Martin( )
4
RETURN 5
IF and and is even   6
Mesh( )
7
RETURN 8
IF is odd or 9
Optimal-Martin( )
10
FOR TO 11
Shift( )
12 13
RETURN 14
Mesh( )
15
FOR TO 16
Shift( )
17 18
RETURN Exercises

29.4-1 Construct a -perfect array (a binary double square for window size .