# Counting And Listing All Permutations

The applet below displays all the permutations of the set _{n} = {1, ..., n},_{0} 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} to get listed on my 100 MHz machine. (In the development environment, N_{8} is permuted faster than N_{7} 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 _{3}. Observing permutations as products of cycles it becomes obvious that elements of S_{3} represent rigid motions of an equilateral triangle. Indeed, envisage such a triangle and mark its vertices with numbers 1,2,3. Then

What if applet does not run? |

The applet offers three algorithms that generate the list of all the permutations: **R**ecursive, **L**exicographic and an algorithm due to B. **H**eap. 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(i-1, j-1); // swap values at positions (i-1) and (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)

### Permutations

- Various ways to define a permutation
- Counting and listing all permutations
- Johnson-Trotter Algorithm: Listing All Permutations

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

63007630 |