Find permutations by repeatedly cycling 3 elements

Question

Is there an algorithm to find all possible permutations of a series of unique elements, that follows this rule?

From a given 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 are possible to be reached via 3-cycles should be found, and the same permutation should not be found twice until all reachable permutations have been found.

Here is an example input:

1,2,3,4,5

Output 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 I have tried to produce such a sequence is the following (for 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 produces the series printed above, but then continues with:

1,2,3,4,5

.. which is a permutation that was already output. Any other algorithm of finding the next 3-cycle I have tried so far failed to find all reachable permutations.

Answer 1

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.