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.

Just a recursive method that finds all permutations of 3 elements, then call that over each set of 3 elements in your input? — OneCricketeer, Jan 16 '16 at 17:22
That way you will find too many results, with lots of duplicates. You can see in the example I gave that cycling the 3 elements on positions 1,2,3 and then cycling the elements on positions 1,2,4 led to a duplicate before all permutations were found. — trincot, Jan 16 '16 at 17:33
I am not sure it is possible, but it is possible to go though permutations with swaps of 2 elements ([[heap's algorithm](https://en.wikipedia.org/wiki/Heap's_algorithm) and [Steinhaus–Johnson–Trotter algorithm](https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm)). — trincot, Jan 16 '16 at 22:21
I don't understand the question, surely a recursive approach that tracks unique combinations already seen should work? — Lasse V. Karlsen, Jan 16 '16 at 22:28
My initial attempt at coding this gave me 60 combinations for 12345: 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. — Lasse V. Karlsen, Jan 16 '16 at 22:29
@LasseV.Karlsen I ran an algorithm that looked at all possible sequences of permutations, and none longer than 60 were found. Starting from ABCDE, you can reach ABDEC and ABECD, but not ABCED, ABDCE or ABEDC; i.e. when keeping two digits, the other three digits can me rotated but not inverted, whatever steps you try inbetween. — m69's been on strike for years, Jan 17 '16 at 05:03
For 5 elements, 60 is indeed the number of permutations that should be listed. For n >= 3, the number of permutations is n!/2, i.e. half the number of permutations that can be achieved without the 3-cycle restriction. — trincot, Jan 17 '16 at 11:00
@trincot Seems that the only way to contact someone on SO is to do so through another post. I refer to your question 'Sort algorithm to create a polygon from points with only right angle' which it seems you have deleted. If you are still interested, I believe I have a solution. If you are interested would you be able to repost your your question so that I can post an answer. Please ping me if you do so. — petern0691, Nov 27 '22 at 11:14
@petern0691, I am not the author of [that question](https://stackoverflow.com/questions/74554553/sort-algorithm-to-create-a-polygon-from-points-with-only-right-angle), but Victor D. I was merely the one who had made the last update to that question. — trincot, Nov 27 '22 at 11:58
Sorry. Thanks. Still trying to understand how this forum is put together. — petern0691, Nov 27 '22 at 19:35

score 7 · Accepted Answer · edited Jan 19 '16 at 09:26

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 tested this, and it works fine. I was a bit afraid the inner loops would badly affect the performance, but it turns out that the total number of iterations in either of these loops never exceeds the number of permutations found. So I think we can say it runs in *O(n!)*, the best one can hope for: great! I put a working Javascript version in this [fiddle](https://jsfiddle.net/1c1s436k/). As you rightly said, the second step to get the 3-cycle steps from this becomes trivial, thanks to the fact that the element in position 0 is swapped at every step. Many thanks! — trincot, Jan 18 '16 at 09:43
@trincot Running through an example using https://oeis.org/A123400 I think that at some points, e.g. when the 4 is first introduced, the triple is rotated in the other direction. Is that OK? — m69's been on strike for years, Jan 18 '16 at 15:26
Thank you for raising that point, @m69. Indeed, for 4 elements Ehrlich's swap method applied in groups of 2 produces the following 3-cycle permutations: *0123 2013 1203 3102 1032...* where the transition to *1031* is a cycle in the opposite direction. But for me it does not matter in which direction the 3 elements cycle. I can see it could be an interesting question to see if an efficient algorithm could deal with such a constraint as well. — trincot, Jan 18 '16 at 16:52

score 2 · Answer 2 · answered Jan 16 '16 at 22:33

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

Thank you for this answer! It does indeed produce the desired output. It does a brute-force search for a solution. Ideally, I would like to know if there is an algorithm where there is no need to check if a permutation was already generated, but the algorithm itself would guarantee that each produced permutation would not have been produced before, much like is done with [heap's algorithm](https://en.wikipedia.org/wiki/Heap's_algorithm). — trincot, Jan 17 '16 at 11:10
@trincot As you'll see in the output, you only have to check every third permutation. The first two permutations rotate the first three digits, the third permutation keeps one or two of the first three digits, then you have another two permutations which rotate the first three digits, ... The permutations which rotate the first three digits don't need checking for duplicates. — m69's been on strike for years, Jan 17 '16 at 20:09
True, @m69. It would be nice though if the algorithm could better predict which permutations to produce. As it is now, I see that for 7 elements this algorithm executes *unique.Contains()* over half a million times; which is quite expensive. A reduction by a factor of 3 is not really changing the order of time needed. The algorithm runs in *O(n!n(n-1)(n-2))*, where I would prefer an algorithm that runs in close to *O(n!)*. — trincot, Jan 18 '16 at 09:20
Is there really any worth in keeping this bruteforce answer around now that a much much better answer has been provided? — Lasse V. Karlsen, Jan 18 '16 at 10:58

m69's been on strike for years · Answer 3 · 2016-06-17T12:30:50.877

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.

This is really awesome! It shows a lot of effort done to come up with a unique, original solution. I tested this for digits between 3 and 11 and it produces correct results (no duplicates, correct number of permutations). The code is also clear and surprisingly compact. Awesome, really awesome ( * bow * ). NB: you could write `first = 1 + ((i % 4 < 2) == (i < 9))` as in JS `true == 1`. A bit shorter would also be: `max = i % 2 : first ? i - 3` — trincot, Feb 06 '16 at 09:38
@trincot Thanks; just trying to live up to my "fanatic" badge :-) In the meantime I've tested it for up to 3200 elements (using the end-state of each previous step as a short-cut to avoid having to generate 3.87e+9828 permutations) and the pattern keeps recurring as expected. Btw, do you think I should store the rotations as triples, just to make it clearer what's happening in the code? — m69's been on strike for years, Feb 07 '16 at 05:54
Nice test! I wouldn't store more than needed. I suppose you are speaking of the `pos` array. It is quite clear that `seq-1` is always the 3rd element index of each cycle. In fact, it really is a pity that you need to store the zero index in each `pos` pair, as you have only one case where it is not zero, but 1. I don't see a nice way to make `pos` just store the middle index and still deal efficiently with the exception, but maybe you do? — trincot, Feb 07 '16 at 09:16
@trincot Every solution I can think of makes the algorithm either less efficienct, harder to understand, or unable to permute just 3 elements, so this is probably the best version to explain the concept. — m69's been on strike for years, Feb 08 '16 at 01:51
@trincot I found a slightly different sequence that doesn't have the 1/2 irregularity between 5 and 9 elements, so the code loses the XOR'ed `i<9` condition during the preparation of the rotation sequences (see update). — m69's been on strike for years, Feb 09 '16 at 03:01
Nice, so now you could write `var first = i % 4 < 2 ? 1 : 2;` as `first = i & 2 ? 2 : 1` or even `first = i & 2 || 1`. — trincot, Feb 09 '16 at 06:32
@trincot I just found a solution that has only 2 types of sequences, for odd and even numbers of elements (see update); I don't think it will get any simpler than this. It doesn't change the code much, but it's easier for humans to remember :-) — m69's been on strike for years, Feb 11 '16 at 06:25
Perfect! Even I can understand the pattern now! Now, get some sleep and put your mind on something else, or you'll get permuted yourself :-) — trincot, Feb 11 '16 at 06:31
Btw, is there any practical application for this, or did you simply ask out of curiosity? It's basically a less efficient and unnecessarily complicated alternative to Heap's algorithm. — m69's been on strike for years, Feb 11 '16 at 21:37
I had looked at Heap's algorithm before, but in its original form I discarded it because it generates consecutive swaps which have no overlapping element, which I needed to translate it into 3-cycles. The reason I asked this question was to be able complete [my answer to another question](http://stackoverflow.com/questions/34656587/solving-rubiks-cubes-for-dummies/34840919#34840919). — trincot, Feb 12 '16 at 12:57

m69's been on strike for years · Answer 4 · 2016-02-06T05:47:57.520

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)

That is a nice find. I can see this question has been keeping you busy! — trincot, Jan 19 '16 at 08:26
@trincot Questions like these are so much more fun than "how to make the footer stick to the bottom of my website using regular expressions". — m69's been on strike for years, Jan 20 '16 at 01:38
Many thanks for this extended answer, @m69! Wonderful! I wonder if there is some erroneous shift of the comments like `2 cycles: [0][1457263]; X=0, Y=1` in the Example section: they seem to apply to the next block (N+1), or otherwise I am completely missing the point. I wish I could give you more than one upvote... your answer certainly deserves some attention. — trincot, Feb 04 '16 at 14:35
@trincot Thanks. Indeed, the resulting cycles and the choice of X and Y are then used in the next step. I didn't want to repeat this info in each next block, because the answer was getting ridiculously long already :-) But maybe I should make this clearer. — m69's been on strike for years, Feb 04 '16 at 15:00
@trincot The example sequence indeed leads to a repeating pattern (although not what I first thought), which makes it possible to write an algorithm for any number of elements (I wrote example code with it in a new answer). — m69's been on strike for years, Feb 06 '16 at 05:46