29.5. 29.5 Three-dimensional perfect arrays

29.5.1. 29.5.1 Pseudocode of the algorithm Colour

Colour transforms cellular perfect arrays into larger cellular perfect arrays. Its input data are

  • – the number of dimensions;

  • – the size of the alphabet;

  • – the window size;

  • – the size of the cellular perfect array ;

  • – a cellular -perfect array.

  • – the multiplication coefficient of the alphabet;

  • – the extension vector having the property .

The output of Colour is

  • a -ary cellular perfect array of size .

Colour consists of four steps:

  1. Blocking (line 1) arranging: copies (blocks) of a cellular perfect array into a rectangular array of size and indexing the blocks lexicographically (by );

  2. Indexing (line 2): the construction of a lexicographic indexing scheme containing the elements and having the same structure as the array , then construction of a colouring matrix , transforming the elements of into -ary numbers consisting of digits;

  3. Colouring (lines 3-4): colouring into a symmetric perfect array using the colouring array that is adding the -fold of the -th element of to each cell of the -th block in (considering the elements of the cell as lexicographically ordered digits of a number).

  4. Report (line 5): returns the output .

The output consists of blocks, blocks consist of cells and cells consists of elements. If is an element of , then the lexicographic index of the block containing is called the blockindex of , the lexicographic index of the cell containing is called the cellindex and the lexicographic index of in the cell is called elementindex . E.g. the element in Table 3 has blockindex 5, cellindex 2 and elementindex 1.

Input parameters are , a cellular -perfect array , the output is a -perfect array , where .

Colour( )

  1  arrange the copies of  into an array  of size  blocks   2  construct a lexicographic indexing scheme  containing the elements       of  and having the same structure as   3  construct an array  transforming the elements of  into -ary        numbers of  digits and multiplying them by   4  produce the output  adding the -th  element of         to each cell of the -th block in  for each block of   5  
                     RETURN
                   
                   
               

29.5.2. 29.5.2 Pseudocode of the algorithm Growing

Finally, algorithm Growing generates a prefix of a growing array . Its input data are , the number of required doubly perfect prefixes of the growing array , then and . It consists of the following steps:

  1. Initialization (line 01): construction of a cellular perfect array using Cellular ;

  2. Resizing (lines 02–14): if the result of the initialization is not doubly symmetric, then construction of a symmetric perfect array using Colour , otherwise we take as ;

  3. Iteration (lines 15–17): construction of the further prefixes of the growing array repeatedly, using Colour .

  4. Report (line 18): returns the output .

Input parameters of Growing are and , the output is a doubly symmetric perfect array , which is the th prefix of an -growing array.

Growing( )

  1  
                     Cellular(
                     
                     )
                     2  calculation of  using formula (29.2)   3  
                     IF
                   
                   is symmetric   4       5  
                     IF
                   
                   is not symmetric   6       7       8       9    
                     FOR
                   
                  
                  
                     TO
                   
                    10         11       
                     Colour(
                     
                     )
                    12    13  
                     FOR
                   
                  
                  
                     TO
                   
                    14      15  
                     FOR
                   
                   
                  
                     TO
                   
                    16      17    
                     Colour(
                     
                     )
                    18  
                     RETURN