Tompkins–Paige algorithm
The Tompkins–Paige algorithm 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. The algorithm for generating all n! permutations of the set is given by the following pseudocode:P ← ;
yield P;
c ← ;
i ← 2;
while i ≤ n do
left-rotate the first i entries of P;
if c < i then
c ← c + 1;
i ← 2;
yield P;
else
c ← 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. Not only does it have to keep track of an auxiliary counting array, redundant permutations are also produced and ignored in the course of generation. For instance, when n = 4, the algorithm will first yield P = and then generate the other 23 permutations in 40 iterations. 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 = c = *111 i=3
P = 2314 c = *121 i=2
P = 3214 c = *221 i=2
P = c = *121 i=3
P = 3124 c = *131 i=2
P = 1324 c = *231 i=2
P = c = *131 i=3
P = c = *111 i=4
P = 2341 c = *112 i=2
P = 3241 c = *212 i=2
P = c = *112 i=3
P = 3421 c = *122 i=2
P = 4321 c = *222 i=2
P = c = *122 i=3
P = 4231 c = *132 i=2
P = 2431 c = *232 i=2
P = c = *132 i=3
P = c = *112 i=4
P = 3412 c = *113 i=2
P = 4312 c = *213 i=2
P = c = *113 i=3
P = 4132 c = *123 i=2
P = 1432 c = *223 i=2
P = c = *123 i=3
P = 1342 c = *133 i=2
P = 3142 c = *233 i=2
P = c = *133 i=3
P = c = *113 i=4
P = 4123 c = *114 i=2
P = 1423 c = *214 i=2
P = c = *114 i=3
P = 1243 c = *124 i=2
P = 2143 c = *224 i=2
P = c = *124 i=3
P = 2413 c = *134 i=2
P = 4213 c = *234 i=2
P = c = *134 i=3
P = c = *114 i=4
P = c = *111 i=5