next (n,pdone)
If n is not 1, then
If n is not at the right end of the current permutation of 1, . . , n then
shift it right one position
else
remove "n" from the current permutation of 1, . . , n
next(n - 1,pdone)
Insert "n" at the left end of the current permutation of 1, . . , n - 1
else
set done to true.
In order to proceed, a data structure to store the permutation must be chosen. To illustrate the effect of this selection, we will use two different structures?/FONT>arrays and lists. We start by storing the permutation in an array p. Searching for the location of n in p will be avoided by keeping an array l of pointers. Both p and l are defined globally. l[n] points to the location of n in p when next(n,pdone) is invoked. Initialize must set p[i] to n - i + 1 and l[i] to 1 for 1 ?/FONT> i ?/FONT> n. Next may be defined as
Figure 4.6(a) simulates the execution of next(4,pdone) when the current permutation is 2 1 3 4.
Now suppose p is implemented as a list whose records are stored in dynamic memory. We need the pointer arrays ptr and pred, which are defined globally, as is the record pointer p. When next(n,pdone) is invoked, ptr[n] will contain a pointer to the record containing n in its information field, and pred[n] will contain a pointer to the predecessor of that record in p. To simplify list shifts and the insertion of a record at the front of p, a dummy record is used as the first record of p. Pred[k] will initially contain a pointer to the dummy record, and ptr[k] will initially contain a pointer to the record of p that contains k, for l ?/FONT> k ?/FONT> n. Now next may be defined as follows:
Figure 4.6(b) simulates the execution of next(4,pdone) when the current permutation is 2 l 3 4.
In comparing the two implementations notice that the advantage of the list implementation is that the for loop required by the array implementation is no longer needed. Inserting n at the left end of the current permutation thus takes only two pointer changes rather than time proportional to n. Other permutation algorithms are explored in Sedgewick [1977].
To further illustrate the differences, two complete programs using function permutations, one for the array and one for the list implementation, are given below. The process function prints each permutation. To adapt these programs to obtain a solution for the stable marriage problem, the function process must test for stability. Another modification would be to abort the execution when a stable pairing is found. This requires that process be given access to done so that it can set done to true at that point.
Array Implementation
List Implementation
next(n,pdone)
/* Generates the next permutation unless
the current one is the last. In this case
done is set to true.
*/
int n,*pdone;
{int i;
if (n > 1)
if (l[n] < n)
{p[l[n]] = p[l[n]+1];
p[l[n]+1] = n;
l[n] = l[n]+1;
}
else
{next(n-1,pdone);
for (i=n-1;i>=1;i--)
p[i+1] = p[i];
p[1] = n;
l[n] = 1;
}
else
*pdone = TRUE;
}
next(n,pdone)
/* Generates the next permutation unless
the current one is the last. In this case
done is set to true.
*/
int n,*pdone;
{if (n > 1)
if (ptr[n]->link != NULL)
{pred[n]->link = ptr[n]->link;
pred[n] = pred[n]->link;
ptr[n]->link = pred[n]->link;
pred[n]->link = ptr[n];
}
else
{pred[n]->link = NULL;
next(n-l,pdone);
ptr[n]->link = p->link;
p->link = ptr[n];
pred[n] = p;
}
else
*pdone = TRUE;
}
(a) Array Implementation for P
(b) List Implementation for P
Figure 4.6 Simulation of NEXT (4,&DONE) When P is 2134
#include <stdio.h>
#define TRUE 1
#define FALSE 0
typedef int arraytype[21];
arraytype p,l;
main()
/* Driver for permutations. */
{int n;
printf("\n n = ?\n");scanf("%d",&n);permutations(n);
}
permutations(n)
/* Generates and processes each
permutation of the integers
1 to n.
*/
int n;
{int done;
done = FALSE;
initialize(n);
while (!done)
{process(n);
next(n,&done);
}
}
initialize(n)
/* Creates initial permutation */
int n;
{int i;
for (i = 1;i<=n;i++)
{p[i] = n - i + 1;
l[i] = 1;
}
}
process(n)
/* Prints the current permutation */
int n;
{int i;
for (i=1;i<=n;i++)
printf("\n%d\n",p[i]);printf("\n");}
next(n,pdone)
/* Generates the next permutation unless
the current one is the last. In this case
done is set to true.
*/
int n,*pdone;
{int i;
if (n > 1)
if (l[n] < n)
{p[l[n]] = p[l[n]1];
p[l[n]+1] = n;
l[n] = l[n]+1;
}
else
{next(n-1,pdone);
for (i=n-1;i>=1;i--)
p[i+1] = p[i];
p[1] = n;
l[n] = 1;
}
else
*pdone = TRUE;
}
#include <stdio.h>
#define TRUE l
#define FALSE 0
#define NULL 0
typedef struct record
{int info;
struct record *link;
}listrecord,*listpointer;
typedef listpointer pointerarray[21];
pointerarray ptr,pred;
listpointer p;
main()
/* Driver for permutations. */
{int n;
printf("\n n = ?\n");scanf("%d",&n);permutations(n);
}
permutations(n)
/* Generates and processes each
permutation of the integers 1 to n.
*/
int n;
{int done;
done = FALSE;
initialize(n);
while (!done)
{process(n);
next(n,&done);
}
}
initialize(n)
/* Creates initial permutation */
int n;
{int i;
listpointer q;
p = malloc(sizeof(listrecord));
q = P;
for (i=1;i<=n;i++)
{q->link = malloc(sizeof(listrecord));
q = q->link;
q->info = n - i + 1;
ptr[n-i+1] = q;
pred[i] = p;
}
q->link = NULL;
}
process(n)
/* Prints the current permutation */
int n;
{listpointer q;
q = p->link;
while (q != NULL)
{printf("\n%d\n",q->info);q = q->link;
}
printf("\n");}
next(n,pdone)
/* Generates the next permutation unless
the current one is the last. In this case
done is set to true.
*/
int n,*pdone;
{if (n > 1)
if (ptr[n]->link != NULL)
{pred[n]->link = ptr[n]->link;
pred[n] = pred[n]->link;
ptr[n]->link = pred[n]->link;
pred[n]->link = ptr[n];
}
else
{pred[n]->link = NULL;
next(n-1,pdone);
ptr[n]->link = p->link;
p->link = ptr[n];
pred[n] = p;
}
else
*pdone = TRUE;
}