## 29.3. 29.3 One-dimensional perfect arrays

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

### 29.3.1. 29.3.1 Pseudocode of the algorithm `Quick-Martin`

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 [].

`Quick-Martin(` `)`

```  1
`FOR`

`TO`

2       3
`FOR`

`TO`

4       5
`FOR`

`TO`

6       7
`FOR`

`TO`

8          9      10      11
`RETURN`

```

This algorithm runs in time.

### 29.3.2. 29.3.2 Pseudocode of the algorithm `Optimal-Martin`

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

`Optimal-Martin(` `)`

```  1
`FOR`

`TO`

2       3
`FOR`

`TO`

4       5     6
`FOR`

`TO`

7       8     9    10
`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 .

### 29.3.3. 29.3.3 Pseudocode of the algorithm `Shift`

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

`Shift(` `)`

```  1
`Optimal-Martin(`

`)`
2
`FOR`

`TO`

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
`RETURN`

```

The running time of `Shift` is .

### 29.3.4. 29.3.4 Pseudocode of the algorithm `Even`

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

`Even(` `)`

```  1
`IF`

2       3       4       5       6
`RETURN W`
7
`FOR`

`TO`

8
`FOR`

`TO`

9         10
`FOR`

`TO`

11         12
`FOR`

`TO`

13         14
`FOR`

`TO`

15         16         17         18         19         20
`RETURN`

```

The running time of algorithm `Even` [] is .

Exercises

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