In the construction of one-dimensional perfect arrays we use the following algorithms.

Algorithm *
Martin
* generates one-dimensional perfect arrays. Its inputs are the alphabet size and the window size . Its output is an -ary perfect sequence of length . The output begins with zeros and always continues with the maximal permitted element of the alphabet.

A natural implementation of Martin's algorithm can be found in the chapter *Complexity of words* of this book. The following effective implementation of *
Martin
* is due to M. Horváth and A. Iványi [
115
].

**
Quick-Martin(
)
**

1`FOR`

2 3`TO`

`FOR`

4 5`TO`

`FOR`

6 7`TO`

`FOR`

8 9 10 11`TO`

`RETURN`

This algorithm runs in time.

The following implementation of Martin algorithm requires even smaller running time than *
Quick-Martin
*.

*
Optimal-Martin(
)
*

1`FOR`

2 3`TO`

`FOR`

4 5 6`TO`

`FOR`

7 8 9 10`TO`

`RETURN`

The running time of any algorithm which constructs a one-dimensional perfect array is , since the sequence contains elements. The running time of *
Optimal-Martin
* is .

Algorithm *
Shift
* proposed by Cock in 1988 [
56
] is a widely usable algorithm to construct perfect arrays. We use it to transform cellular -perfect arrays into -perfect arrays.

*
Shift(
)
*

12`Optimal-Martin(`

`)`

`FOR`

3 transform to an digit -ary number 4 produce the -st layer of the output by multiple shifting the th layer of by the transformed number (the first digits give the shift size for the first direction, then the next digits in the second direction etc.) 5`TO`

`RETURN`

The running time of *
Shift
* is .

If is even, then this algorithm generates the -length prefix of an even growing sequence [ 119 ].

*
Even(
)
*

12 3 4 5 6`IF`

7`RETURN W`

`FOR`

8`TO`

`FOR`

9 10`TO`

`FOR`

11 12`TO`

`FOR`

13 14`TO`

`FOR`

15 16 17 18 19 20`TO`

`RETURN`

The running time of algorithm *
Even
*
[
119
] is .

**Exercises**

29.3-1 Solve the **telex problem**, that is construct a -perfect array (using *
?
*).