Counting And Listing All Permutations
The applet below displays all the permutations of the set Nn = {1,...,n},
where n changes from 0 to 7. N0 is of course empty. There is no special reason for
selecting 7 as the upper size of the allowed sets - the algorithms described below are quite general.
The problem is that of speed. I did not have enough patience to wait for the 7! = 5040 permutations
of N7 to get listed on my 100 MHz machine. (In the development environment, N8 is
permuted faster then N7 in a browser. P.S. This has been written in 1997!) Thus beware.
In the applet, every permutation is also presented as a product of cycles.
For n = 3, we have a list of 6 elements of the symmetric group S3. Observing permutations as products of cycles it becomes obvious that elements of S3 represent rigid motions of an equilateral triangle. Indeed, envisage such a triangle and mark its vertices with numbers 1,2,3. Then (1 2 3) denotes the rotation of the vertices wherewith 1 goes to 2, 2 to 3, and 3 to 1. (1 3 2) is a rotation in the opposite direction. (1 2)(3) is the symmetry around the median from vertex 3, and so on.
The applet offers three algorithms that generate the list of all the permutations: Recursive, Lexicographic and an algorithm due to B. Heap. I'll describe each in turn. In all the algorithms, N denotes the number of items to be permuted.
Recursive algorithm
The recursive algorithm is short and mysterious. It's executed with a call visit(0). Global variable level
is initialized to -1 whereas every entry of the array Value is initialized to 0.
void visit(int k)
{
level = level+1; Value[k] = level; // = is assignment
if (level == N) // == is comparison
AddItem(); // to the list box
else
for (int i = 0; i < N; i++)
if (Value[i] == 0)
visit(i);
level = level-1; Value[k] = 0;
}
void AddItem()
{
// Form a string from Value[0], Value[1], ... Value[N-1].
// At this point, this array contains one complete permutation.
// The string is added to the list box for display.
// The function, as such, is inessential to the algorithms.
}
Try this algorithm by hand to make sure you undestand how it works.
Lexicographic order and finding the next permutation
Permutation f precedes a permutation g in the lexicographic
(alphabetic) order iff for the minimum value of k such that
f(k) g(k), we have f(k) < g(k). Starting with
the identical permutation f(i) = i for all i, the second algorithm generates sequentially
permutaions in the lexicographic order. The algorithm is described in [Dijkstra, p. 71].
void getNext()
{
int i = N - 1;
while (Value[i-1] >= Value[i]) i = i-1;
int j = N;
while (Value[j-1] <= Value[i-1]) j = j-1;
// swap values at positions (i-1) and (j-1)
swap(i-1, j-1);
i++; j = N;
while (i < j)
{
swap(i-1, j-1);
i++;
j--;
}
}
B. Heap's algorithm
Heap's short and elegant algorithm is implemented as a recursive method HeapPermute [Levitin, p. 179]. It is invoked with HeapPermute(N).
void HeapPermute(int n)
{
if (n == 1)
AddItem();
else {
for (int i = 0; i < n; i++)
HeapPermute(n-1);
if (n % 2 == 1) // if n is odd
swap(0, n-1);
else // if n is even
swap(i, n-1);
}
Reference
- A. Levitin, Introduction to The Design & Analysis of Algorithms, Addison Wesley, 2003
- E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997 [FACSIMILE] (Paperback)
- R. Sedgewick, Algorithms in C, Addison-Wesley, 3rd edition (August 31, 2001)
Copyright © 1996-2009 Alexander Bogomolny
|