Different order generation algorithm

Question

I am trying to write a simple algorithm that generates different sets

(cba) (cab) (bac) (bca) (acb) from (abc)

by performing two operations:

swap first and second input elements (abc), so I get (bac)

then shift the first element to last => input (bac), the output will be (acb)

therefore, the final conclusion of this procedure is (acb).

Of course, this method only generates cb and ab c. I was wondering if it is possible to use these two operations (possibly using 2 exchanges per line and then shift or any variation) to create all different orders?

I would like to come up with a simple algorithm without using> <or +, simply by repeatedly exchanging some positions (for example, always exchanging positions 1 and 2) and always changing certain positions (for example, shifting the 1st element to the last).

Answer 1

Note that the shift operation (moving the first element to the end) is equivalent to allowing the swap of any adjacent pair: you simply shift until you reach the pair you want to swap, and then swap the elements.

So your question is essentially equivalent to the following question: is it possible to generate each permutation using only the swap park. And if so, is there an algorithm for this.

The answer is yes (to both questions). One of the algorithms for this is called the Johnson-Trotter algorithm, and you can find it on Wikipedia .