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
  1. Tompkins, C. (1956). "Machine attacks on problems whose variables are permutations". Proc. Symposium in Appl. Math., Numerical Analysis. 6. McGraw–Hill, Inc., N.Y. pp. 195–211.
  2. Sedgewick, Robert (1977). "Permutation Generation Methods". Computing Surveys. 9 (2): 137–164. doi:10.1145/356689.356692.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.