Tompkins–Paige algorithm

The Tompkins-Paige algorithm^[1] is an algorithm for generating all permuatations of the 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 permutation P. If the algorithm is implemented correctly, this statement will be executed exactly n! times, each with a different permutation P.

This algorithm is not the the most efficient one among all existing permutation generation methods^[2]. Not only does it have to keep track of an auxilliary counting array (c), redundant permutations are also produced and discarded in the course of generation.

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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
^ Sedgewick, Robert (1977). "Permutation Generation Methods". Computing Surveys. 9 (2): 137–164.

[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. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)

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

[1]

[2]