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 *
Mesh
* was proposed by Iványi and Tóth in 1988. The input of

`Mesh`

*
Mesh(
)
*

1`FOR`

2`TO`

`FOR`

3`TO`

is even 4 5`IF`

6`ELSE`

`RETURN`

Algorithm *
Cellular
* is an extension and combination of the known algorithms

`Shift, Optimal-Martin, Even`

`Mesh`

*
Cellular
* results a cellular perfect array . Its input data are and , its output is an -perfect array, where and for .

`Cellular`

*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`Optimal-Martin`

*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`Martin`

`Shift`

*Combination*(lines 13–16): if is even and , then construct an even sequence with`Even`

`Mesh`

`Shift`

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

*
Cellular(
)
*

1 23`IF`

4`Optimal-Martin(`

`)`

5`RETURN`

and and is even 6`IF`

7`Mesh(`

`)`

8`RETURN`

is odd or 9`IF`

10`Optimal-Martin(`

`)`

`FOR`

11`TO`

12 13`Shift(`

`)`

14`RETURN`

15`Mesh(`

`)`

`FOR`

16`TO`

17 18`Shift(`

`)`

`RETURN`

**Exercises**

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