        Next: Generating Subsets Up: Combinatorial Problems Previous: Median and Selection

## Generating Permutations Input description: An integer n.

Problem description: Generate (1) all or (2) a random or (3) the next permutation of length n.

Discussion: A permutation describes an arrangement, or ordering, of things. Many algorithmic problems in this catalog seek the best way to order a set of objects, including traveling salesman (the least-cost order to   visit n cities), bandwidth (order the vertices of a graph   on a line so as to minimize the length of the longest edge), and graph isomorphism   (order the vertices of one graph so that it is identical to another). Any algorithm for solving such problems exactly must construct a series of permutations along the way.

There are n! permutations of n items, which grows so quickly that you can't expect to generate all permutations for n > 11, since 11! = 39,916,800.   Numbers like these should cool the ardor of anyone interested in exhaustive search and help explain the importance of generating random permutations.

Fundamental to any permutation-generation algorithm is a notion of order, the sequence in which the permutations are constructed, from first to last.   The most natural generation order is lexicographic, the order they would appear if they were sorted numerically. Lexicographic order for n=3 is , , , , , and finally . Although lexicographic order is aesthetically pleasing, there is often no particular reason to use it. For example, if you are searching through a collection of files, it does not matter whether the filenames are encountered in sorted order, so long as you search through all of them. Indeed, nonlexicographic orders lead to faster and simpler permutation generation algorithms.

There are two different paradigms for constructing permutations: ranking/unranking and incremental change methods.     Although the latter are more efficient, ranking and unranking can be applied to solve a much wider class of problems, including the other combinatorial generation problems in this book. The key is to define functions rank and unrank on all permutations p and integers n, m, where |p| = n and .

• Rank(p) - What is the position of p in the given generation order?   A typical ranking function is recursive, such as , with . Getting this right means relabeling the elements of the smaller permutation to reflect the deleted first element. Thus • Unrank(m,n) - Which permutation is in position m of the n! permutations of n items?   A typical unranking function finds the number of times (n-1)! goes into m and proceeds recursively. Unrank(2,3) tells us that the first element of the permutation must be `2', since but . Deleting from m leaves the smaller problem Unrank(0,2). The ranking of 0 corresponds to the total order, and the total order on the two remaining elements (since `2' has been used) is , so .

What the actual rank and unrank functions are does not matter as much as the fact that they must be inverses.   In other words, p = Unrank(Rank(p), n) for all permutations p. Once you define ranking and unranking functions for permutations, you can solve a host of related problems:

• Sequencing permutations -   To determine the next permutation that occurs in order after p, we can Rank(p), add 1, and then Unrank(p). Similarly, the permutation right before p in order is Unrank(Rank(p)-1,|p|). Counting through the integers from 0 to n!-1 and unranking them is equivalent to generating all permutations.
• Generating random permutations -   Select a random integer from 0 to n!-1 and unrank it.
• Keep track of a set of permutations - Suppose we want to construct random permutations and act only when we encounter one we have not seen before.   We can set up a bit vector (see Section )   with n! bits, and set bit i to 1 if permutation Unrank(i,n) has been seen.   A similar technique was employed with k-subsets in the Lotto application of Section .

The rank/unrank method is best suited for small values of n, since n! quickly exceeds the capacity of machine integers, unless arbitrary-precision arithmetic is available (see Section ).   The incremental change methods work by defining the next and previous operations to transform one permutation into another, typically by swapping two elements. The tricky part is to schedule the swaps so that permutations do not repeat until all of them have been generated. See the output picture above for an ordering of the six permutations of with a single swap between successive permutations.

Incremental change algorithms for sequencing permutations are tricky, but they are concise enough that they can be expressed in a dozen lines of code. See the implementation section for pointers to code.    Because the incremental change is a single swap, these algorithms can be extremely fast - on average, constant time - which is independent of the size of the permutation! The secret is to represent the permutation using an n-element array to facilitate the swap. In certain applications, only the change between permutations is important. For example, in a brute-force program to search for the optimal tour, the cost of the tour associated with the new permutation will be that of the previous permutation, with the addition and deletion of four edges.

Throughout this discussion, we have assumed that the items we are permuting are all distinguishable.     However, if there are duplicates (meaning our set is a multiset), you can save considerable time and effort by avoiding identical permutations. For example, there are only ten permutations of , instead of 120.   To avoid duplicates use backtracking and generate the permutations in lexicographic order.

Generating random permutations is an important little problem that people stumble across often, and often botch up. The right way is the following two-line, linear-time algorithm. We assume that Random[i,n] generates a random integer between i and n, inclusive.

```

for i=1 to n do a[i] = i;

for i=1 to n-1 do swap[ a[i], a[ Random[i,n] ];

```

That this algorithm generates all permutations uniformly at random is not obvious.   If you think so, explain convincingly why the following algorithm does not generate permutations uniformly:

```

for i=1 to n do a[i] = i;

for i=1 to n-1 do swap[ a[i], a[ Random[1,n] ];

```

Such subtleties demonstrate why you must be very careful with random generation algorithms. Indeed, we recommend that you try some reasonably extensive experiments with any random generator before really believing it. For example, generate 10,000 random permutations of length 4 and see whether all 24 of them occur approximately the same number of times.   If you understand how to measure statistical significance, you are in even better shape.

Implementations: The best source on generating combinatorial objects is Nijenhuis and Wilf [NW78], who provide efficient Fortran implementations of algorithms to construct random permutations    and to sequence permutations in minimum-change order.   Also included are routines to extract the cycle structure of a permutation. See Section for details.

An exciting WWW site developed by Frank Ruskey of the University of Victoria contains a wealth of material on generating combinatorial objects of different types, including permutations, subsets, partitions, and certain graphs. Specifically, there is an interactive interface that lets you specify which type of objects you would like to construct and quickly returns the objects to you. It is well worth checking this out at http://sue.csc.uvic.ca/ cos/.

Combinatorica [Ski90] provides Mathematica implementations of algorithms that construct random permutations and sequence permutations in minimum change and lexicographic orders.     It also provides a backracking routine to construct all distinct permutations of a multiset, and it supports various permutation group operations. See Section .

The Stanford GraphBase (see Section ) contains routines to generate all permutations of a multiset.

Notes: The primary reference on permutation generation is the survey paper by Sedgewick [Sed77]. Good expositions include [NW78, RND77, Rus97].

The fast permutation generation methods make only a single swap between successive permutations. The Johnson-Trotter algorithm [Joh63, Tro62] satisfies an even stronger condition, namely that the two   elements being swapped are always adjacent.

In the days before ready access to computers, books with tables of random permutations [MO63] were used instead of algorithms.   The swap-based random permutation algorithm presented above was first described in [MO63].

Related Problems: Random number generation (see page ), generating subsets (see page ), generating partitions (see page ).        Next: Generating Subsets Up: Combinatorial Problems Previous: Median and Selection

Algorithms
Mon Jun 2 23:33:50 EDT 1997