Find permutations by repeatedly cycling 3 elements
In my previous answer to this question, I described a method to find sequences of same-direction 3-element rotations that will generate all (reachable) permutations of N elements. The simplest sequence I could find with this method is used in the implementation below. The rotations for each number of elements show a recurring pattern, different only for odd/even values of N; this means that the sequence of rotations can easily be generated for any number of elements.
N=3: (0,1,2) (0,1,2)
N=4: (0,1,3) (1,2,3) (1,2,3)
N=5: (0,3,4) (0,3,4) (0,3,4) (0,3,4)
N=6: (0,1,5) (0,2,5) (0,2,5) (0,2,5) (0,2,5)
N=7: (0,5,6) (0,5,6) (0,5,6) (0,5,6) (0,5,6) (0,5,6)
N=8: (0,1,7) (0,2,7) (0,3,7) (0,4,7) (0,4,7) (0,4,7) (0,4,7)
...
Starting from 5 elements, you'll find this recurring pattern:
N=odd: (0,N-2,N-1) (0,N-2,N-1) (0,N-2,N-1) ...
N=even: (0,1,N-1) (0,2,N-1) (0,3,N-1) ... (0,N-4,N-1) (0,N-4,N-1) (0,N-4,N-1) (0,N-4,N-1)
Or graphically, with < denoting the position of the rotated elements:
N=3 N=4 N=5 N=6 N=7 N=8 N=9 N=10 N=11 N=12
<<< <<=< <==<< <<===< <====<< <<=====< <======<< <<=======< <========<< <<=========<
<<< =<<< <==<< <=<==< <====<< <=<====< <======<< <=<======< <========<< <=<========<
=<<< <==<< <=<==< <====<< <==<===< <======<< <==<=====< <========<< <==<=======<
<==<< <=<==< <====<< <===<==< <======<< <===<====< <========<< <===<======<
<=<==< <====<< <===<==< <======<< <====<===< <========<< <====<=====<
<====<< <===<==< <======<< <=====<==< <========<< <=====<====<
<===<==< <======<< <=====<==< <========<< <======<===<
<======<< <=====<==< <========<< <=======<==<
<=====<==< <========<< <=======<==<
<========<< <=======<==<
<=======<==<
Generating the permutations is then done by running through the sequences of rotations in this order, where every n-th n is replaced by n+1 :
3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,6, ...
so that the rotations are:
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,3,4),
(0,1,2), (0,1,2), (0,1,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (1,2,3), (0,1,2), (0,1,2), (0,1,5), ...
The code example below generates the rotation sequences up to the requested number of elements, and then carries out the rotations and outputs the resulting permutations.
function rotate3permute(elems) {
// GENERATE ROTATION SEQUENCES
var pos = [,,,[[0,1],[0,1]],[[0,1],[1,2],[1,2]]];
for (var i = 5; i <= elems; i++) {
pos[i] = [];
for (var j = 1; j < i; j++) pos[i].push([0, i % 2 ? i - 2 : j < i - 4 ? j : i - 4])
}
// PREPARE INITIAL PERMUTATION AND STEP COUNTER
var perm = [0,1], step = [,,,], seq = 3;
for (var i = 2; i < elems; i++) {
perm.push(i);
step.push(0);
}
document.write(perm + "<BR>");
// EXECUTE ROTATIONS
while (seq <= elems) {
rotate(pos[seq][step[seq]++], seq - 1);
document.write(perm + "<BR>");
seq = 3;
while (step[seq] == seq - 1) step[seq++] = 0; // seq = 3,3,4,3,3,4,3,3,4,3,3,5...
}
function rotate(pair, third) {
var temp = perm[pair[0]];
perm[pair[0]] = perm[pair[1]];
perm[pair[1]] = perm[third];
perm[third] = temp;
}
}
rotate3permute(8);Note: replace while (step[seq] == seq - 1) with while (seq <= elems && step[seq] == seq - 1) in stricter languages, to avoid array out-of-bounds errors.
As mentioned, to generate all permutations and not just the half that can be reached by 3-element rotation, output every permutation twice, once as-is and once with the first two elements switched.
Building N-element permutations
To generate permutations of N elements by repeatedly rotating 3 elements in the same direction, you can build a 4-element permutation from the 3-element rotation, then a 5-element permutation from the 4-element permutation, and so on, until you reach N elements.
E.g. the 3-element rotation is as follows:
012
<<< 120
<<< 201
The 4-element permutation repeatedly uses the 3-element rotation, alternated by a rotation in which the 4th element is rotated:
0123
<<< 1203
<<< 2013
<<=< 0312
<<< 3102
<<< 1032
<<=< 0231
<<< 2301
<<< 3021
=<<< 3210
<<< 2130
<<< 1320
(where < is the postion of an element that is rotated, and = is the position of an element that remains in place.)
The 5-element permutaton repeats the 4-element permutation, alternated by a rotation in which the 5th element is rotated:
01234 <=<=< 23401 <=<=< 40123 <=<=< 12340 <=<=< 34012
<<< 12034 <<< 34201 <<< 01423 <<< 23140 <<< 40312
<<< 20134 <<< 42301 <<< 14023 <<< 31240 <<< 03412
<<=< 03124 <<=< 20341 <<=< 42013 <<=< 14230 <<=< 31402
<<< 31024 <<< 03241 <<< 20413 <<< 42130 <<< 14302
<<< 10324 <<< 32041 <<< 04213 <<< 21430 <<< 43102
<<=< 02314 <<=< 24031 <<=< 41203 <<=< 13420 <<=< 30142
<<< 23014 <<< 40231 <<< 12403 <<< 34120 <<< 01342
<<< 30214 <<< 02431 <<< 24103 <<< 41320 <<< 13042
=<<< 32104 =<<< 04321 =<<< 21043 =<<< 43210 =<<< 10432
<<< 21304 <<< 43021 <<< 10243 <<< 32410 <<< 04132
<<< 13204 <<< 30421 <<< 02143 <<< 24310 <<< 41032
Defining an N-element permutation
For each step from N-1 to N elements, there are several options, each with their own end-state. Each step is thus defined by N-1 rotations, and together they define an N-element permutation; e.g. for the above example:
3 ELEMENTS
rotations: <<< <<<
complete permutation: 012 -> 201
4 ELEMENTS
rotations: <<=< <<=< =<<<
complete permutation: 0123 -> 1320
5 ELEMENTS
rotations: <=<=< <=<=< <=<=< <=<=<
complete permutation: 01234 -> 41032
Selecting rotations
You'll see in the above examples that the 4-element permutation doesn't use 3 identical rotations, but instead <<=<, again <<=< and finally =<<<; that is because not every combination of possible rotations creates a correct permutation.
To find which rotations you can use for an N-element permutation, look at the end-state of the N-1-element permutation, and see which cycles it contains, e.g.:
Permutation 0123 -> 1320 has two cycles: [031] and [2], because position 0 moves to position 3, position 3 moves to position 1, and position 1 moves to position 0, while position 2 stays in place.
Permutation 0123 -> 3210 has two cycles: [03] and [12], because 0 and 3 switch places, and 1 and 2 switch places.
case: multiple cycles
To create an N-element permutation from an N-1-element permutation, you need to rotate two elements from the first N-1 elements with the N-th element. Check which cycles the N-1-element permutation has, and select rotation points at position 0, and at a position in a second cycle. Repeat this rotation as many times as there are elements in the second cycle, then move the second point to a position in the third cycle (if there is one), and repeat this as many times as there are elements in the third cycle, and so on. When all cycles have been used, repeat the last rotation as necessary.
An example will make this clearer:
N-1-permutation: 012345 -> 254301
cycles: [042], [15], [3]
0123456 ... 2543016
<<====< 5643012 ... 4103562 (positions 0 and 1, for cycle [15])
<<====< 1203564 ... 0653124 (repeat for second element in [15])
<==<==< 3654120 ... 5214360 (positions 0 and 3, for cycle [3])
<==<==< 4210365 ... 1630425 (done; repeat last rotation till end)
<==<==< 0635421 ... 3245061
<==<==< 5241063 ... 4601523
As you will notice, in the case of 2 cycles, the rotation stays the same throughout:
N-1-permutation: 012345 -> 354201
cycles: [0423], [15]
0123456 ... 3542016
<<====< 5642013 ... 2104563 (positions 0 and 1, for cycle [15])
<<====< 1304562 ... 4650132 (repeat for second element in [15])
<<====< 6250134 ... 0315624 (done; repeat last rotation till end)
<<====< 3415620 ... 5261340
<<====< 2061345 ... 1436205
<<====< 4536201 ... 6023451
case: one cycle
Find two positions X and Y, where X is to the left of Y, the N-1 permutation moves X to Y, and Y is not the right-most position in the N-1 permutation. Then rotate positions X and Y with the Nth element repeatedly, and for the final step rotate Y and the right-most position.
Again, an example will make this clearer:
N-1-permutation: 012345 -> 153024
cycles: [032451]
positions X and Y: e.g. 0 and 3, because 0 moves to 3 and 3 < 5 (other option: 2 and 4)
0123456 ... 1530246
<==<==< 0536241 ... 5460321 (positions X and Y)
<==<==< 0461325 ... 4210635 (repeat until penultimate rotation)
<==<==< 0215634 ... 2350164
<==<==< 0354162 ... 3640512
<==<==< 0642513 ... 6120453
===<=<< 6125430 ... 1356240 (last rotation: position Y and right-most)
There is an edge case when the N-1 permutation consists of 1-position shifts in the same direction as the rotation; in this case, alternate between positions 0 and 1 and positions 1 and 2:
N-1-permutation: 012345 -> 123450
cycles: [054321]
0123456 ... 1234506
<<====< 2634501 ... 6345021
=<<===< 6415023 ... 4150263
<<====< 1350264 ... 3502614
=<<===< 3042615 ... 0426135
<<====< 4526130 ... 5261340
=<<===< 5601342 ... 6013452
Example of rotation selection
Here is an example for permutations up to 10 elements; there are many options, but this one shows an interesting repeating pattern starting from 7 elements (compare the rotations used for 7 and 9 elements and for 8 and 10 elements, and also the end state for 7 and 9 elements):
THREE ELEMENTS (3 permutations)
012
<<< 120
<<< 201 = 1 cycle: [012] X=0, Y=1
FOUR ELEMENTS (12 permutations)
0123 ... 2013
<<=< 0312 ... 1032
<<=< 0231 ... 3021
=<<< 3210 ... 1320 = 2 cycles: [031][2] X=0, Y=2
FIVE ELEMENTS (60 permutations)
01234 ... 13204
<=<=< 23401 ... 30421
<=<=< 40123 ... 02143
<=<=< 12340 ... 24310
<=<=< 34012 ... 41032 = 3 cycles: [024][1][3] X=0, Y=1,3
SIX ELEMENTS (360 permutations)
012345 ... 410325
<<===< 150324 ... 251304
<==<=< 351402 ... 053412
<==<=< 453210 ... 154230
<==<=< 254031 ... 352041
<==<=< 052143 ... 450123 = 2 cycles: [024][135] X=0, Y=1
SEVEN ELEMENTS (2,520 permutations)
0123456 ... 4501236
<<====< 5601234 ... 2356014
<<====< 3456012 ... 0134562
<<====< 1234560 ... 5612340
<<====< 6012345 ... 3460125
<<====< 4560123 ... 1245603
<<====< 2345601 ... 6023451 = 5 cycles: [016][2][3][4][5]; X=0, Y=2,3,4,5
EIGHT ELEMENTS (20,160 permutations)
01234567 ... 60234517
<=<====< 20734516 ... 12734506
<==<===< 32764501 ... 03764521
<===<==< 43761520 ... 24761530
<====<=< 54761032 ... 35761042
<====<=< 05761243 ... 40761253
<====<=< 20761354 ... 52761304
<====<=< 32761405 ... 03761425 = 2 cycles: [0][1457263]; X=0, Y=1
NINE ELEMENTS (181,440 permutations)
012345678 ... 037614258
<<======< 387614250 ... 365281740
<<======< 605281743 ... 624708513
<<======< 234708516 ... 271530486
<<======< 761530482 ... 758463102
<<======< 528463107 ... 540126837
<<======< 470126835 ... 413872065
<<======< 153872064 ... 186057324
<<======< 846057321 ... 802345671 = 7 cycles: [018][2][3][4][5][6][7]; X=0, Y=2,3,4,5,6,7
TEN ELEMENTS (1,814,400 permutations)
0123456789 ... 8023456719
<=<======< 2093456718 ... 1293456708
<==<=====< 3298456701 ... 0398456721
<===<====< 4398156720 ... 2498156730
<====<===< 5498106732 ... 3598106742
<=====<==< 6598102743 ... 4698102753
<======<=< 7698102354 ... 5798102364
<======<=< 3798102465 ... 6398102475
<======<=< 4398102576 ... 7498102536
<======<=< 5498102637 ... 3598102647 = 2 cycles: [051483][2679]; X=0, Y=2
Generating the permutations
Generating permutations is done by first selecting which rotations to use, and then executing the rotations using the following sequence, in which every third 3 is replaced by a 4, every fourth 4 is replaced by a 5, every fifth 5 is replaced by a 6, and so on:
3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,5,3,3,4,3,3,4,3,3,4,3,3,6...
which is similar to Ehrlich's sequence, in that you can use the first 2 rotations to generate the 3 permutations of 3 elements, or the first 11 for the 12 permutations for 4 elements, or the first 59 for the 60 permutations of 5 elements, or in general: N!/2-1 rotations to generate N!/2 permutations.
(update: for an implementation, see my other answer to this question.)
Unreachable permutations
As was mentioned in the question and comments, only half of the possible permutations can be generated using 3-element rotation. Every permutation generated with the method above has an unreachable companion permutation, which can be created by switching the first two elements, e.g.:
0123 (1023)
<<< 1203 (2103)
<<< 2013 (0213)
<<=< 0312 (3012)
<<< 3102 (1302)
<<< 1032 (0132)
<<=< 0231 (2031)
<<< 2301 (3201)
<<< 3021 (0321)
=<<< 3210 (2310)
<<< 2130 (1230)
<<< 1320 (3120)
There is this old paper V. L. Kompel'makher and V. A. Liskovets. Sequential generation of arrangements by a basis of transpositions., which shows that you can generate all permutations by means of simple transpositions and each of this transpositions must swap the first element of the permutation with any of other (so called star shaped basis). For example for S(3) that would be, as the first element (opposed to element 1) is swapped in every step.
123->213->312->132->231->321->[123, Hamiltonian cycle!]
There is also a similar approach A `Hot Potato' Gray Code for Permutations which is not behind a pay wall. An important insight of this paper is, that even if in every transposition element 1 must be swapped, still all permutations can be generated without repetition (element 1 is swapped in every step):
123->213->231->132->312->321->[123, Hamiltonian cycle!]
Another algorithm for cycling through all permutations for the star shaped basis is this one from Knuths "The Art of computer programming", Chapter "Generating all permutations". Algorithm is called "Ehrlich's swap method". I don't claim to understand what is going on there, it is only a translation of the algorithm into java. The most interesting part for you is that line here:
//swap values to get next permutation:
swap(per,0,b[k]);
In every step there is a transposition and in every transposition the element[0] is swapped (->star shaped basis).
import java.util.Arrays;
public class EhrlichPermuter {
//Follows Knuths "The Art of computer programming", Chapter "Generating all permutations", "Ehrlich's swap method".
int n;
int[] c;
int[] b;
int[] per;
boolean done;
void initialize(){
c=new int[n];
b=new int[n];
per=new int[n];
for(int j=0;j<n;j++){
b[j]=j;
per[j]=j;
}
}
EhrlichPermuter(int n){
this.n=n;
initialize();
}
void swap(int[] a, int i, int j){
int h=a[i];a[i]=a[j];a[j]=h;
}
int[] getNextPermut(){
int[] result=Arrays.copyOf(per, per.length);//remember permutation
int k=1;
while(c[k]>=k){
c[k]=0;
k++;
if(k==n){
done=true;
initialize();//we got all permutations so far
return result;//return the last permutation
}
}
c[k]=c[k]+1;
//swap values to get next permutation:
swap(per,0,b[k]);
//flip:
int j=1; k--;
while(j<k){
swap(b,j,k);
j++;
k--;
}
return result;//return remembered permutation
}
}
Now the hard stuff is done!
The last step is: Any two consecutive transpositions of the form (1 a)(1 b) can be written as a 3-element cycle (1 a b). Thus you would just jump over permutation with negative parity. For Hot-Potato this looks as follows
123 --(213)-->231--(132)-->312--(321)-->[123, Hamiltonian cycle!]
with permutations in () skipped.
I'm pretty sure I didn't get this question as it sounds like you already have all the pieces you need to implement it but here goes. Please leave a comment whether this sounds correct or not.
I went for a recursive approach. Cycle every combination of 3 elements, then recursively handle the new combination. Only deal with unique combinations.
Here is the code implemented as a C# program in LINQPad:
void Main()
{
var unique = new HashSet<string>();
Traverse(unique, "12345");
string.Join(", ", unique).Dump();
}
public static void Traverse(HashSet<string> unique, string digits)
{
if (unique.Contains(digits))
return;
unique.Add(digits);
for (int index1 = 0; index1 < digits.Length; index1++)
for (int index2 = 0; index2 < digits.Length; index2++)
{
if (index2 == index1)
continue;
for (int index3 = 0; index3 < digits.Length; index3++)
{
if (index3 == index1 || index3 == index2)
continue;
var c = digits.ToCharArray();
char temp = c[index1];
c[index1] = c[index2];
c[index2] = c[index3];
c[index3] = temp;
Traverse(unique, new string(c));
}
}
}
The output:
12345, 23145, 31245, 14235, 42135, 21435, 13425, 34125, 41325, 15324, 53124, 31524, 12534, 25134, 51234, 13254, 32154, 21354, 14352, 43152, 31452, 15432, 54132, 41532, 13542, 35142, 51342, 45312, 53412, 34512, 42513, 25413, 54213, 41253, 12453, 24153, 45123, 51423, 14523, 43521, 35421, 54321, 42351, 23451, 34251, 45231, 52431, 24531, 32541, 25341, 53241, 43215, 32415, 24315, 52314, 23514, 35214, 15243, 52143, 21543