CODEWITHSUNDEEP
algorithmlanguage-agnostic
Abramo K.
Abramo K.

Reputation: 63

Algorithm for generating different orders

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

(c b a) (c a b) (b a c) (b c a) (a c b) from (a b c)

by doing two operations:

exchange first and second elements of input (a b c) , So I get (b a c)

then shift first element to last = > input is (b a c), output is (a c b)

so final output of this procedure is (a c b).

Of course, this method only generates a c b and a b c. I was wondering if using these two operations (perhaps using 2 exchange in a row and then a shift, or any variation) is enough to produce all different orderings?

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

Upvotes: 6

Views: 149

Answers (1)

Omri Barel
Omri Barel

Reputation: 9490

Note that the shift operation (move the first element to the end) is equivalent to allowing an exchange (swap) of any adjacent pair: you simply shift until you get to 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 every permutation using only adjacent-pair swap. And if it is, is there an algorithm to do that.

The answer is yes (to both questions). One of the algorithms to do that is called "The Johnson–Trotter algorithm" and you can find it on Wikipedia.

Upvotes: 5

Related Questions