2003-10-22

How to: Enumerate permutations

Problem: Enumerate all permutations of a set M.

Solution: Assign an integer value x, with x in [0..|M!|), to each permutation P by the following algorithm:

Algorithm 1:
1. for i := 0 to |M|-1 do
    1.1. T[i] := Phi(P(Phi^-1(i))), where phi:M->[0..|M|) is bijective.
2. x := 0
3. for i := |M|-1 downto 1 do
    3.1. y := T[i]
    3.2. Delete element i from the array T.
    3.3. for j := 0 to i-1 do
        3.3.1. if T[j] > y then T[j] := T[j] - 1
    3.4. x := x*(i + 1) + y
4. Return x.

Proposition 1: Algorithm 1 describes a bijective function F from the set of permutations over M to the interval [0..|M|!).

Proof: Note that an increment of |M| will only entail additional steps in the loops at step 1 and 3. Hence the proposition can be proved with mathematical induction. 

Firstly, note that if |M| = 1 then there is exactly one permutation and x will always be 0. 

Secondly, assume that the theorem is true for all M such that |M| < n, for some integer n. (By the pidgeon hole principle and since the set of permutations over M has the same cardinality as the interval [0..|M|!), we only have to prove injectivity.) Suppose that there are two permutations P and P' such that F(P) = F(P') = x. If P is not equal to P', then there is a value i such that P(i) is not equal to P'(i).

Suppose that i = |M|-1. But then we have that F(P)/(|M|!-1) is not equal to F(P')/(|M|!-1), making it impossible that F(P) = F(P').

Suppose instead that i < |M|-1. If, at the second execution of the loop at 3, the array T describes a permutation in both cases, then we have a contradiction by induction, because that would imply that either F(P) is not equal to F(P'), or P = P'. So suppose that the second value of T (in either case) is not a permutation over the set [0..|M|-1). This is only possible if either there is a j such that T[j] is greater than or equal to |M|-1, or there are j, k such that j is not equal to k and T[j] = T[k]. Both alternatives are made impossible by the fact that P is a permutation, and by loops 1 and 3.3:

The former alternative: If the second value of T[j] is equal to or greater than |M|-1, then either Phi(P(j)) or Phi(P(j+1)) must be greater than or equal to |M|, and that contradicts the assumption that P is a permutation over M.

The latter alternative: Suppose that the second value of T[j] = T[k] is greater than or equal to the first value of y. This entails that both values have been decremented by the first execution of the loop 3.3, hence that these elements had the same value to begin with (but either might have been moved by step 3.2), and that contradicts the assumption that P is a permutation. The same argument applies if the second value of T[j] = T[k] is less than the first value of y, because then either value might have been moved by step 3.2, but both have retained their original values.

Q.E.D.

Remark: Since F_M(P) is an enumeration of permutations over the set M, it is a bijective function. Hence, for each integer x in the interval [0..|M|!), there is exactly one permutation P such that F_M(P) = x. This means that the inverse of algorithm 1 can be used to assign a unique permutation over M for each integer in the set [0..|M|!).

©2000StreamSec