Suppose you decided to implement configuration as a list of records stored in dynamic memory, and to use n as a pointer to the nth record of the configuration list. Figure 3.16 depicts these assumptions graphically for ten cards.
Perfectshuffle must, consecutively, move 6 before 2, 7 before 3, 8 before 4, and finally 9 before 5. Two pointers, l1 and n, are shown in Figure 3.16. Traversing configuration and processing the records pointed to by l1 and n will accomplish the movements, if the processing deletes the successor of the record pointed to by n, inserts this deleted record after the record pointed to by l1, and updates l1 to point to it. Move carries out this processing task.
Perfectshuffle may now be implemented by
configurationpointer l1,newn;
l1 = configuration;
newn = l1;
while(l1 != n)
{
move(l1,n);
l1 =l1->link;
newn = newn->link;
}
n = newn;
Perfectshuffle in this form is a refinement of traverse. Move plays the role of process. It uses local variables hold1 and hold2 to keep track of the successors needed:
move(pl1,n)
configurationpointer *pl1,n;
{
configurationpointer hold1,hold2;
hold1 = l1->link;
hold2 = n->link;
11->link = hold2;
n->link = hold2->link;
hold2->link = hold1;
l1 = l1->link;
}
Two complete programs that output the number of shuffles are presented at the end of this paragraph. The first is based on an array, and the second on a list implementation. In this case there is nothing to recommend the list implementation over the array implementation, since the configuration does not grow or shrink (except for the artificial limit on the array size that would be required by the array implementation). The two versions of perfectshuffle are both useful for the application to which we return in the section that follows the programs.
Array Implementation
List Implementation
#define TRUE 1
#define FALSE 0
typedef int arraytype[53];
main() /* Perfect shuffle using arrays */
/* Drives the perfectshuffle */
{arraytype configuration;
int numbershuffles,n;
printf("\n Enter an integer between 1 and 26 \n");scanf("%d",&n);initial(configuration,n);
numbershuffles = 1;
perfectshuffle(configuration,n);
while(!original(configuration,n))
{perfectshuffle(configuration,n);
numbershuffles++;
}
printf("\n Number of shuffles = %d \n",numbershuffles);}
initial(configuration,n)
/* Creates the initial configuration */
arraytype configuration;
int n;
{int i;
for(i=1;i<=(2*n);i++)
configuration[i] = i;
}
perfectshuffle(configuration,n)
/* Carries out a perfect shuffle */
arraytype configuration;
int n;
{arraytype result;
int i,newi;
i = 1;
newi = 1;
while(i < (n+1))
{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];
}
original(configuration,n)
/* Returns true if the original
configuration has recurred
*/
arraytype configuration;
int n;
}
int i,temporiginal;
i = 1;
temporiginal = TRUE;
while((i < (n+1))&&temporiginal)
if(configuration[i] != i)
temporiginal = FALSE;
else
i++;
return(temporiginal);
}
#define TRUE 1
#define FALSE 0
#define NULL 0
typedef struct configrec
{int info;
struct configrec *link;
}configrecord,*configptr;
int num;
main() /* perfect shuffle using lists */
/* Drives the perfectshuffle */
{configptr configuration,n;
int numbershuffles;
printf("\n Enter an integer between 1 and 26\n");scanf("%d",&num);initial(&configuration,&n);
numbershuffles = 1;
perfectshuffle(configuration,&n);
while(!original(configuration,n))
{perfectshuffle(configuration,&n);
numbershuffles++;
}
printf("\n The number of shuffles = %d\n",numbershuffles);}
initial(pconfiguration,pn)
/* Creates the initial configuration */
configptr *pconfiguration,*pn;
{configptr p,q;
int i;
*pconfiguration = malloc(sizeof(configrecord));
p = *pconfiguration;
i = 1;
while(i != (2*num+1))
{p->info = i;
if(i == num)
*pn = p;
i++;
p->link = malloc(sizeof(configrecord));
q = p;
p = p->link;
}
q->link = NULL;
}
perfectshuffle(configuration,pn)
/* Carries out a perfect shuffle */
configptr configuration,*pn;x
{configptr l1,newn;
l1 = configuration;
newn = l1;
while(l1 != *pn)
{move(&l1,*pn);
l1 = l1->link;
newn = newn->link;
}
*pn = newn;
}
original(configuration,n)
/* Returns true if the original
configuration has recurred
*/
configptr configuration,n;
{int temporiginal,i;
configptr p;
temporiginal = TRUE;
i = 1;
p = configuration;
while((p != n->link)&&temporiginal)
if(p->info != i)
temporiginal = FALSE;
else
{i++;
p = p->link;
}
return(temporiginal);
}
move(pl1,n)
/* Processes a record of configuration */
configptr *pl1,n;
{configptr hold1,hold2;
hold1 = (*pl1)->link;
hold2 = n->link;
(*pl1)->link = hold2;
n->link = hold2->link;
hold2->link = hold1;
(*pl1) = (*pl1)->link;
}