3.9.2 Array Implementation of the Perfect Shuffle

Suppose we decide to implement configuration as an array and use n as a pointer to the card in position n. Then initial and original may be defined, respectively by

>Comment

for(i=1;i<=(2*n);i++)

configuration[i] = i;

and

>Comment

temporiginal = TRUE;

i = 1;

while((i<n+1)&&temporiginal)

if(configuration[i] != i)

temporiginal = FALSE;

else

i++;

original = temporiginal;

Perfectshuffle is somewhat more complex. The first and last cards, 1 and 2n, never change position in configuration. After the shuffle, cards 1 and n + 1, 2 and n + 2, 3 and n + 3, . . . , i and n + i . . . , and n and 2n will appear in consecutive positions in the resultant configuration. An array, result, is used to hold the new configuration. In traversing the relevant n positions of configuration (the 0th is ignored), its ith entry is processed by copying configuration[i] and configuration[i+n] into their proper new consecutive positions in result. I serves as a pointer to the current entry of configuration being processed, and newi will point to the new position of that entry in result. The situation, when n is 6, is depicted in Figure 3.15(a) just before the fourth entry is to be processed.

If the following statements are executed

>Comment

result[newi] = configuration[i];

result[newi+1] = configuration[i+n];

i++;

newi = newi + 2;

then the program will have properly processed the ith and (i+n)th cards. It will also have updated i and newi so that they are pointing to the proper new positions, in configuration and result, respectively. The situation after the fourth element has been processed is as shown in Figure 3.15(b).

To complete the shuffle, result can be copied into configuration. A program segment for perfectshuffle might be as follows.

>Comment

i = 1;

while(i < n)

{

result[newi] = configuration[i];

result[newi+1] = configuration[i+n];

i++;

newi = newi + 2;

}

for(i=1;i<=(2*n);i++)

configuration[i] = result[i];

Notice that the solution involves a number of array traversals, each traversal processing accessed elements in a different way.

(a) Situation Just before the Fourth Entry Is Processed

(b) Situation Just after the Fourth Entry Is Processed

Figure 3.15 Two Arrays Used for a Perfect Shuffle of Six Elements