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". 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.
 |  |
