algorithm - Find permutations by repeatedly cycling 3 elements -

is there algorithm find possible permutations of series of unique elements, follows rule?

from given permutation next permutation must found cycling 3 elements. can 3 elements.

with such 3-cycles subset of permutations found, possible reached via 3-cycles should found, , same permutation should not found twice until reachable permutations have been found.

here example input:

1,2,3,4,5 

output 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 many algorithms have tried produce such sequence following (for array a , length n):

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

this produces series printed above, continues with:

1,2,3,4,5 

.. permutation output. other algorithm of finding next 3-cycle have tried far failed find reachable permutations.

there old paper v. l. kompel'makher , v. a. liskovets. sequential generation of arrangements basis of transpositions., shows can generate permutations means of simple transpositions , each of transpositions must swap first element of permutation of other (so called star shaped basis). example s(3) be, first element (opposed element 1) swapped in every step.

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

there similar approach a `hot potato' gray code permutations not behind pay wall. important insight of paper is, if in every transposition element 1 must swapped, still permutations can generated without repetition (element 1 swapped in every step):

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

another algorithm cycling through permutations star shaped basis 1 knuths "the art of computer programming", chapter "generating permutations". algorithm called "ehrlich's swap method". don't claim understand going on there, translation of algorithm java. interesting part line here:

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

in every step there transposition , in every transposition element[0] swapped (->star shaped basis).

import java.util.arrays;  public class ehrlichpermuter {     //follows knuths "the art of computer programming", chapter "generating 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 permutations far                 return result;//return last permutation             }         }         c[k]=c[k]+1;          //swap values 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 hard stuff done!

the last step is: 2 consecutive transpositions of form (1 a)(1 b) can written 3-element cycle (1 b). jump on permutation negative parity. hot-potato looks follows

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

with permutations in () skipped.