Mani is a senior programmer/analyst at a mutual-funds company in Boston. He has a masters degree in Computer Science from the University of Bombay, India and is a CCP. Mani can be reached at [email protected].
In his classic paper "Permutation Generation Methods" (Computing Surveys 9, 1977), Robert Sedgewick surveys the various permutation generation methods published until then, categorizing them as follows:
- Methods based on exchanges in which the n! permutations of n are obtained by a series of (n!-1) exchanges. Algorithms proposed by M.B. Wells, J. Boothroyd, B.R. Heap, S.M. Johnson, H.F. Trotter, and F.M. Ives fall into this category.
- Algorithms not based on exchanges. Some algorithms, for instance, use cyclic rotations to obtain the n! permutations. One such algorithm is by G.W. Langdon (I arrived at his method independently). Other algorithms proposed by Fischer and Krause and R.J. Ord-Smith generate lexicographic permutations.
The algorithm I propose here generates permutations in a novel way, using cyclic rotations (implemented without hardware dependencies) and matrices. The only restrictions on the implementation language are the availability of a "string copy" function and efficient pointer manipulations.
The Algorithm
The first step toward generating all n! permutations of 1,2,...,n is to generate the pivot permutations. A pivot permutation is obtained by certain rules and is used to generate an nxn matrix, which in turn yields 2n permutations. Consequently, you need n!/2n pivot permutations. Before discussing pivot-permutation generation, however, certain definitions are in order.
A "permutation" is a sequence of pi, where i=1,2,...,n and pi is a unique integer between 1 and n, inclusive. The function right rotate(f,l) of a permutation yields a sequence where pf=pl and pi=pi-1 for i=f+1,...,l.
The function left rotate(f,l) of a permutation yields a sequence where pl=pf and pi=pi+1 for i=f,...,l-1. A "full-right rotate" and a "full-left rotate" are special cases where f=1 and l=n.
A "cyclic-permutation matrix" is an nxn matrix whose first row is a pivot permutation and whose ith row is obtained by a full-right rotate of the (i-1)th row for i=2,...,n. In all rotations, f (first) is 
l (representing last).
Pivot permutations are obtained by performing rotations, right or left, but only in one direction throughout the process. For the purpose of this discussion, I'll stick with right rotate, although left works equally well.
Successive pivot permutations are generated using (n-1) right rotates with l=(n-1). The nth right rotate will yield the starting sequence; you can refer to these as (n-1)th order pivots. Using each of the (n-1) pivots, generate the (n-2)th order pivots using (n-2) right rotates with l=(n-2). Continue the process until l=2, at which point no more pivot permutations can be generated, leaving you with n!/2n pivot permutations. The fact that the nth right rotate of an nth order pivot permutation yields the original sequence in the (n+1)th order implies that the third-order pivots are the ones actually used to generate the nxn matrices.
For a given third-order pivot permutation, using this pivot permutation as the first row of an nxn matrix, generate the other (n-1) rows of the cyclic-permutation matrix by performing (n-1) full-right rotates. After creating the matrix, read the rows and columns of the matrix to yield 2n permutations. Repeating the process for the other pivot permutations will yield (n!/2n)x2n=n! permutations.
Figure 1 and Figure 2 show the algorithm generating all permutations of 1,2,3,4, and 5 (that is, n=5). Reading the rows and the columns of the 12 matrices in Figure 2 yields the 120 permutations of {1,2,3,4,5}. Consequently, the algorithm can be coded recursively in an elegant manner; see Example 1. Listing One is the complete C implementation of the permutation-generation algorithm. The array num, which is one relative, is defined as a character array to facilitate using character pointers in the memcpy functions and building the cyclic-permutation matrices via an array of pointers.
In rightRotate(f,l), the right rotates are performed by cloning the substring of num indexed by f and having length l into the array temp, which is zero relative. The final result is obtained by getting the string from temp, indexed by (l-1) and having length l. For example, if num={0,3,2,4,1,5} and a rightRotate (1,4) needs to be performed, then the first and second memcpy functions from num to temp would yield temp equal to {3,2,4,1,3,2,4,1}. The string indexed by 3 and having length 4 in temp is copied back into num indexed by 1, thus yielding num as equal to {0,1,3,2,4,5}.
In createCyclicMatrix(), the entire array num is cloned into temp, and the pointer array p is created by pointing to the different indexes of temp. Since a cyclic-permutation matrix is created by performing (n-1) full-right rotates on the pivot permutation, it is only natural to create the matrix as an array of pointers. For example, if a cyclic-permutation matrix needs to be created for the pivot permutation stored in num as {0,2,4,1,3,5}, then temp would be equal to {2,4,1,3,5,2,4,1,3,5} and p would be created as described in Table 1. The permutations are obtained by reading the n rows and n columns of the cyclic-permutation matrix stored in p.
Salient Features of the Algorithm
Any of the n! permutations of n can be used as an initial permutation to generate the n! permutations of n. This is because every permutation of n must be either a row or a column of a cyclic-permutation matrix and any row or column of the matrix can be used as a pivot permutation to generate the matrix.
The cyclic-permutation matrix can be created using full-left rotates, but the matrix will have to be created bottom up; that is, the pivot permutation is the nth row of the matrix, and for i=(n-1),...,1, the ith row is created by performing a full-left rotate on the (i+1)th row.
The ith order pivot permutations can be created using one of the following:
- Right rotate (1,i).
- Left rotate (1, i).
- Right rotate (n-i+1, n).
- Left rotate (n-i+1, n).
In the cyclic-permutation matrix, the primary diagonals or the secondary diagonals, depending on the direction of rotates used (primary for right and secondary for left), have the same number. This is true for the ixi matrix obtained by the ith order pivot permutations; for example, the matrix obtained by (1,i) elements or (n-i+1) elements of the i pivot permutations. The uniqueness of the permutations can be attributed to this property.
Conclusion
Sedgewick notes that the exchange method by B.R. Heap will run fastest on most computers. In Data Structures and Program Design in C (Prentice-Hall, 1991), Robert L. Kruse, Bruce P. Leung, and Clovis L. Tondo claim that the linked-list, or simple-exchange algorithm is at least as efficient as the Heap method. Both the Heap and linked-list algorithms have been implemented using the C programs supplied by Kruse et al. in their book. I've used these programs for performance comparisons to the Matrix method, on a 486-based PC running under DOS and a Sun workstation under Solaris. The results are as follows:
- If the processing of a given permutation is implemented as a simple printf function resulting in mere enumeration of the permutations, the Matrix method is only slightly faster than the Heap and linked-list methods. This slight difference may be attributed to the integer conversion involved in the printing of a character.
- If the processing of a given permutation is implemented as a dummy function, the Matrix method is faster than the other two methods by a factor of two.
Figure 1: Generating pivot permutations
Copyright © 1995, Dr. Dobb's Journal
Fifth-order Fourth-order Third-order
Pivot Pivot Pivot
1 2 3 4 5 4 1 2 3 5 2 4 1 3 5
1 2 4 3 5
4 1 2 3 5
3 4 1 2 5 1 3 4 2 5
4 1 3 2 5
3 4 1 2 5
2 3 4 1 5 4 2 3 1 5
3 4 2 1 5
2 3 4 1 5
1 2 3 4 5 3 1 2 4 5
2 3 1 4 5
1 2 3 4 5
Figure 2: Cyclic-permutation matrices generated by the 12 pivot permutations.
[ 2 4 1 3 5 ] [ 1 2 4 3 5 ] [ 4 1 2 3 5 ] [ 1 3 4 2 5 ] [ 4 1 3 2 5 ]
[ 5 2 4 1 3 ] [ 5 1 2 4 3 ] [ 5 4 1 2 3 ] [ 5 1 3 4 2 ] [ 5 4 1 3 2 ]
[ 3 5 2 4 1 ] [ 3 5 1 2 4 ] [ 3 5 4 1 2 ] [ 2 5 1 3 4 ] [ 2 5 4 1 3 ]
[ 1 3 5 2 4 ] [ 4 3 5 1 2 ] [ 2 3 5 4 1 ] [ 4 2 5 1 3 ] [ 3 2 5 4 1 ]
[ 4 1 3 5 2 ] [ 2 4 3 5 1 ] [ 1 2 3 5 4 ] [ 3 4 2 5 1 ] [ 1 3 2 5 4 ]
[ 3 4 1 2 5 ] [ 4 2 3 1 5 ] [ 3 4 2 1 5 ] [ 2 3 4 1 5 ] [ 3 1 2 4 5 ]
[ 5 3 4 1 2 ] [ 5 4 2 3 1 ] [ 5 3 4 2 1 ] [ 5 2 3 4 1 ] [ 5 3 1 2 4 ]
[ 2 5 3 4 1 ] [ 1 5 4 2 3 ] [ 1 5 3 4 2 ] [ 1 5 2 3 4 ] [ 4 5 3 1 2 ]
[ 1 2 5 3 4 ] [ 3 1 5 4 2 ] [ 2 1 5 3 4 ] [ 4 1 5 2 3 ] [ 2 4 5 3 1 ]
[ 4 1 2 5 3 ] [ 2 3 1 5 4 ] [ 4 2 1 5 3 ] [ 3 4 1 5 2 ] [ 1 2 4 5 3 ]
[ 2 3 1 4 5 ] [ 1 2 3 4 5 ]
[ 5 2 3 1 4 ] [ 5 1 2 3 4 ]
[ 4 5 2 3 1 ] [ 4 5 1 2 3 ]
[ 1 4 5 2 3 ] [ 3 4 5 1 2 ]
[ 3 1 4 5 2 ] [ 2 3 4 5 1 ]
Example 1: Recursive algorithm for generating permutations by the matrix method.
matrixPermute (n)
{
if (n = 3) createCyclicMatrix
and return;
for (n - 1) times
{
rightRotate (1, n - 1);
matrixPermute (n - 1);
}
}
Table 1: Simulation of the cyclic-permutation matrix by an array of pointers.
i p[i] *(p[i]+0) *(p[i]+1) *(p[i]+2) *(p[i]+3) *(p[i]+4)
0 temp+5 2 4 1 3 5
1 temp+4 5 2 4 1 3
2 temp+3 3 5 2 4 1
3 temp+2 1 3 5 2 4
4 temp+1 4 1 3 5 2
Listing One
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX 20
char num[MAX + 1];
int n;
main (int argc, char *argv[])
{
int i;
void matrixPermute (), createCyclicMatrix (), rightRotate ();
if (argc != 2)
{
fprintf (stderr, "Usage: permute <string>\n");
exit (1);
}
n = atoi (argv [1]);
if (n < 3 || n > MAX)
{
fprintf (stderr, "number must be between 3 and %d\n", MAX);
exit (1);
}
for (i = 1; i <= n; ++i)
num [i] = i;
matrixPermute (n);
}
void matrixPermute (int k)
{
int i, temp;
if (k == 3)
{
createCyclicMatrix ();
return;
}
temp = k - 1;
for (i = 0; i < temp ; ++i)
{
rightRotate (1, temp);
matrixPermute (temp);
}
}
void createCyclicMatrix ()
{
char *p[MAX], temp[2*MAX];
int i, j;
/* create the cyclic permutation matrix P as an array of pointers */
memcpy (temp, num + 1, n);
memcpy (temp + n , num + 1, n);
for (i = 0; i < n; ++i)
p[i] = temp + n - i;
/* generate the 2n permutations from the cyclic permutation matrix P */
for (i = 0; i < n; ++i)
{
/* print the ith row */
for (j = 0; j < n; ++j)
printf ("%d ", *(p[i] + j));
printf ("\n");
/* print the ith column */
for (j = 0; j < n; ++j)
printf ("%d ", *(p[j] + i));
printf ("\n");
}
}
void rightRotate (int f, int l)
{
char temp [2*MAX], *saveptr;
int i;
saveptr = num + f;
memcpy (temp , saveptr, l);
memcpy (temp + l, saveptr, l);
memcpy (saveptr, temp + l - 1, l);
}
