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

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

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

Exercises

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