Tompkins–Paige algorithm

The Tompkins–Paige algorithm^[1] is a computer algorithm for generating all permutations of a finite set of objects.

The method

Let P and c be arrays of length n with 1-based indexing (i.e. the first entry of an array has index 1). The algorithm for generating all n! permutations of the set {1, 2, ..., n} is given by the following pseudocode:

P ← [1, 2, ..., n];
yield P;
c ← [*, 1, ..., 1]; (the first entry of c is not used)
i ← 2;
while i ≤ n do
    left-rotate the first i entries of P;
    (e.g. left-rotating the first 4 entries of
    [4, 2, 5, 3, 1] would give [2, 5, 3, 4, 1])
    if c[i] < i then
        c[i] ← c[i] + 1;
        i ← 2;
        yield P;
    else
        c[i] ← 1;
        i ← i+1;

In the above pseudocode, the statement "yield P" means to output or record the set of permuted indices P. If the algorithm is implemented correctly, P will be yielded exactly n! times, each with a different set of permuted indices.

This algorithm is not the most efficient one among all existing permutation generation methods.^[2] Not only does it have to keep track of an auxiliary counting array (c), redundant permutations are also produced and ignored (because P is not yielded after left-rotation if c[i] ≥ i) in the course of generation. For instance, when n = 4, the algorithm will first yield P = [1,2,3,4] and then generate the other 23 permutations in 40 iterations (i.e. in 17 iterations, there are redundant permutations and P is not yielded). The following lists, in the order of generation, all 41 values of P, where the parenthesized ones are redundant:

P =  1234  c = *111  i=2
P =  2134  c = *211  i=2
P = (1234) c = *111  i=3
P =  2314  c = *121  i=2
P =  3214  c = *221  i=2
P = (2314) c = *121  i=3
P =  3124  c = *131  i=2
P =  1324  c = *231  i=2
P = (3124) c = *131  i=3
P = (1234) c = *111  i=4
P =  2341  c = *112  i=2
P =  3241  c = *212  i=2
P = (2341) c = *112  i=3
P =  3421  c = *122  i=2
P =  4321  c = *222  i=2
P = (3421) c = *122  i=3
P =  4231  c = *132  i=2
P =  2431  c = *232  i=2
P = (4231) c = *132  i=3
P = (2341) c = *112  i=4
P =  3412  c = *113  i=2
P =  4312  c = *213  i=2
P = (3412) c = *113  i=3
P =  4132  c = *123  i=2
P =  1432  c = *223  i=2
P = (4132) c = *123  i=3
P =  1342  c = *133  i=2
P =  3142  c = *233  i=2
P = (1342) c = *133  i=3
P = (3412) c = *113  i=4
P =  4123  c = *114  i=2
P =  1423  c = *214  i=2
P = (4123) c = *114  i=3
P =  1243  c = *124  i=2
P =  2143  c = *224  i=2
P = (1243) c = *124  i=3
P =  2413  c = *134  i=2
P =  4213  c = *234  i=2
P = (2413) c = *134  i=3
P = (4123) c = *114  i=4
P = (1234) c = *111  i=5

References

^ Tompkins, C. (1956). "Machine attacks on problems whose variables are permutations". Proc. Symposium in Appl. Math., Numerical Analysis. Vol. 6. McGraw–Hill, Inc., N.Y. pp. 195–211.
^ Sedgewick, Robert (1977). "Permutation Generation Methods". Computing Surveys. 9 (2): 137–164. doi:10.1145/356689.356692.

[Tompkins-1] Tompkins, C. (1956). "Machine attacks on problems whose variables are permutations". Proc. Symposium in Appl. Math., Numerical Analysis. Vol. 6. McGraw–Hill, Inc., N.Y. pp. 195–211.

[Sedgewick-2] Sedgewick, Robert (1977). "Permutation Generation Methods". Computing Surveys. 9 (2): 137–164. doi:10.1145/356689.356692.

[1]

[2]