Find permutations by repeatedly cycling 3 elements

Question

Is there an algorithm for finding all possible permutations of a number of unique elements that follow this rule?

From this permutation, the next permutation must be found by cycling exactly 3 elements. They can be any three elements.

With such 3-cycles, only a subset of all permutations will be found, but all those that can be achieved through 3-cycles must be found, and the same permutation should not be found twice until all available permutations are found.

Here is an example input:

1,2,3,4,5 

The conclusion could be:

 3,1,2,4,5 2,3,1,4,5 4,2,1,3,5 3,4,1,2,5 1,3,4,2,5 4,1,3,2,5 2,4,3,1,5 

... etc.

One of the many algorithms that I tried to create such a sequence is as follows (for an array a and length n):

 print (a) for i = 0 to n-1 for j = i+1 to n-1 for l = j+2 to n-1 for k = j+1 to l cycle a[i],a[j],a[k] print (a) cycle a[i],a[j],a[k] print (a) 

This creates the series printed above, but then continues:

 1,2,3,4,5 

.. which is already a permutation. Any other search algorithm for the next 3-cycle, which I still have not found, could not find all valid permutations.

Answer 1

There is this old article by V. L. Compapelmacher and V. A. Liskovets. Sequential generation of arrangements based on transpositions. , which shows that you can generate all the permutations using simple transpositions, and each of these transpositions should change the first element of the permutation to any other (the so-called star-shaped basis). For example, for S (3), which would be, since the first element (opposite element 1) is replaced at each step.

 123->213->312->132->231->321->[123, Hamiltonian cycle!] 

There is also a similar “Gray Hot Potato Code” approach for permutations that does not stand behind a toll wall. An important understanding of this article is that even if you need to swap each transpose element 1, all permutations can be generated without repetition (element 1 is replaced at each step):

 123->213->231->132->312->321->[123, Hamiltonian cycle!] 

Another cycling algorithm for all permutations for a star-shaped form is one of The Knut, The Art of Computer Programming, the chapter Generating All Permutations. The algorithm is called the "Ehrlich exchange method". I do not claim to understand what is happening there, this is just a translation of the algorithm in java. The most interesting part for you is this line:

  //swap values to get next permutation: swap(per,0,b[k]); 

At each step there is a transposition, and in each transposition the element [0] is replaced (-> star-shaped).

 import java.util.Arrays; public class EhrlichPermuter { //Follows Knuths "The Art of computer programming", Chapter "Generating all permutations", "Ehrlich 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 complicated stuff is done!

Last step: any two consecutive transpositions of the form (1 a) (1 b) can be written as a 3-element cycle (1 ab). That way, you just jump over the permutation with negative parity. For Hot Potato, it looks like this

 123 --(213)-->231--(132)-->312--(321)-->[123, Hamiltonian cycle!] 

with permutations in () skipped.

Answer 2

In my previous answer to this question, I described a method of searching for sequences of three-dimensional turns with one direction that will generate all (achievable) permutations of N elements. The simplest sequence that I could find using this method is used in the implementation below. Rotations for each number of elements show a repeating pattern that is different only for odd / even N values; this means that a rotation sequence can be easily 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 with 5 elements, you will find this repeating 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 <<< <<=< <==<< <<===< <====<< <<=====< <======<< <<=======< <========<< <<=========< <<< =<<< <==<< <=<==< <====<< <=<====< <======<< <=<======< <========<< <=<========< =<<< <==<< <=<==< <====<< <==<===< <======<< <==<=====< <========<< <==<=======< <==<< <=<==< <====<< <===<==< <======<< <===<====< <========<< <===<======< <=<==< <====<< <===<==< <======<< <====<===< <========<< <====<=====< <====<< <===<==< <======<< <=====<==< <========<< <=====<====< <===<==< <======<< <=====<==< <========<< <======<===< <======<< <=====<==< <========<< <=======<==< <=====<==< <========<< <=======<==< <========<< <=======<==< <=======<==< 

The permutation generation is performed by performing sequences of turns 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 rotation:

(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 following code example generates rotation sequences up to the requested number of elements, and then rotates and displays 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) with more strict languages ​​to avoid errors out of range.

As already mentioned, to generate all permutations, and not just half that can be achieved using three-dimensional rotation, output each permutation twice, once as is, and once when the first two elements switch.

Answer 3

I am sure that I did not have this question, because it seems that you already have everything you need to implement it, but here. Please leave a comment if this sounds correct or not.

I went for a recursive approach. Loop each combination of three elements, and then recursively process the new combination. Use only 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)); } } } 

Exit:

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.

Answer 4

Creating permutations of N-elements

To create permutations of N elements by repeatedly rotating three elements in the same direction, you can build a 4-element permutation of 3-element rotation, then a permutation of 5 elements of 4-element permutation, etc., until you reach N items.

eg. 3-element rotation is as follows:

  012 <<< 120 <<< 201 

The 4-element permutation reuses the 3-element rotation, alternating with the rotation in which the 4th element rotates:

  0123 <<< 1203 <<< 2013 <<=< 0312 <<< 3102 <<< 1032 <<=< 0231 <<< 2301 <<< 3021 =<<< 3210 <<< 2130 <<< 1320 

(where < is the position of the element that is rotated, and = is the position of the element that remains in place.)

The 5-element permutation repeats the 4-element permutation, alternating with the rotation in which the 5th element rotates:

  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 

Definition of permutation of N-elements

For each step from N-1 to N elements, there are several options, each with its own final state. Thus, each step is determined by the rotation of N-1, and together they determine the permutation of N-elements; for example 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 

Corner selection

In the above examples, you will see that the 4-element permutation does not use 3 identical rotations, but instead <<=< again <<=< and finally =<<< ; because not every combination of possible turns creates the right permutation.
To find which rotations you can use to rearrange N-elements, look at the final state of the permutation of N-1 elements and see what cycles it contains, for example:

The permutation 0123 -> 1320 has two cycles: [031] and [2] , since position 0 moves to position 3, position 3 moves to position 1, and position 1 moves to position 0, and position 2 remains in place.

The permutation 0123 -> 3210 has two cycles: [03] and [12] , since the switching points are 0 and 3, as well as the switching points 1 and 2.

case: several loops

To create a permutation of N-elements from a permutation of N-1-elements, you need to rotate two elements from the first elements of N-1 using the N-th element. Check in which cycles the permutation of N-1 elements is located, and select the rotation points at position 0 and at the position in the second cycle. Repeat this rotation as many times as there are in the second cycle, then move the second point to the position in the third cycle (if there is one) and repeat this as many times as there are elements in the third cycle, and soon. When all cycles have been used, repeat the last turn if necessary.

An example will make this clear:

 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 noticed, in the case of 2 cycles, the rotation remains the same in everything:

 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 loop

Find two positions X and Y, where X is to the left of Y, the permutation N-1 moves X to Y, and Y is not the rightmost position in the permutation N-1. Then rotate the X and Y positions alternately with the Nth element, and for the final step, rotate Y and the rightmost position.

Again, an example will make this clear:

 N-1-permutation: 012345 -> 153024 cycles: [032451] positions X and Y: eg 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 a boundary case when the permutation N-1 consists of 1-position shifts in the same direction as the rotation; in this case, alternate 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 

Rotation Selection Example

Here is an example of permutations of up to 10 elements; There are many options, but this shows an interesting repeating pattern, starting with 7 elements (compare the turns used for 7 and 9 elements, and for 8 and 10 elements, as well as the final 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 

Create lookups

Permutations are generated by selecting the first turns, and then making turns using the following sequence, in which every third 3 is replaced by 4, every fourth 4 is replaced by 5, every fifth 5 is replaced by 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 the Ehrlich sequence, since you can use the first 2 rotations to generate 3 permutations of three elements or the first 11 for 12 permutations for 4 elements or for the first 59 for 60 permutations of 5 elements or in general: N! / 2-1 rotations for generating N! / 2 permutations.

(update: for implementation, see my other answer to this question.)

Inaccessible permutations

As already mentioned in the question and comments, only half of the possible permutations can be generated using 3-element rotation. Each permutation generated using the method described above has an unattainable permutation of companions, which can be created by switching the first two elements, for example:

  0123 (1023) <<< 1203 (2103) <<< 2013 (0213) <<=< 0312 (3012) <<< 3102 (1302) <<< 1032 (0132) <<=< 0231 (2031) <<< 2301 (3201) <<< 3021 (0321) =<<< 3210 (2310) <<< 2130 (1230) <<< 1320 (3120)