1
$\begingroup$

I've red this article many-many times, as well as some more supplementary reading on groups, permutations, generating sets etc. and I give up. :( I'm not a mathematician (I study combinatorics, but I'm not there yet, so I can handle a moderate amount of terminology).

My problem: I want to write a function that generates successive unique permutations of a sequence of an arbitrary length by swapping two elements of the sequence at a time.

What I don't understand in the article: what are the numbers inside the parenthesis. Are they the offset into the sequence or are they members of the sequence? How long is the sequence being discussed? (two elements long, or five?) What do the dots between parenthesis mean? It is not / can't be a dot product or multiplication or function composition - but I can't find any more meanings / searching for dot is clearly unproductive...

Ideally, I would be most happy if you took a sequence of 3 (better 4, but it might be a lot of work - so I'm not asking to do it all, if it's 4) and do something like this:

  1. ABCD - swap A and B because
  2. BACD - swap B and C because
  3. CABD - ...

In case you are bored / have no time to write one - below is an example I've found empirically - but I can't formulate the algorithm for producing permutations for the sequence of a given length.

1   1 2 3 4    #(0 1 2) 1 |     - -                   | 2   2 1 3 4 *  #(0 1 2) 2 |     -   -                 | 3   3 1 2 4    #(0 0 2) 2 |     - -                   | 4   1 3 2 4    #(0 1 2) 2 |     -   -                 | 5   2 3 1 4    #(0 0 2) 2 |     - -                   | 6   3 2 1 4 ** #(0 1 2) 3 |     -     -               | 7   4 2 1 3    #(0 1 1) 3 |       -   -               | 8   4 3 1 2    #(0 1 0) 3 |       - -                 | 9   4 1 3 2    #(0 0 2) 3 |       -   -               | 10  4 2 3 1    #(0 0 1) 3 |       - -                 | 11  4 3 2 1    #(0 0 0) 3 |       -   -               | 12  4 1 2 3 +  #(0 1 2) 3 |     -   -                 | 13  2 1 4 3    #(0 1 1) 3 |     -     -               | 14  3 1 4 2    #(0 1 0) 3 |      - -                   | 15  1 3 4 2    #(0 0 2) 3 |     -     -               | 16  2 3 4 1    #(0 0 1) 3 |     - -                   | 17  3 2 4 1    #(0 0 0) 3 |     -     -               | 18  1 2 4 3 +  #(0 1 2) 3 |       - -                 | 19  1 4 2 3    #(0 1 1) 3 |     -     -               | 20  3 4 2 1    #(0 1 0) 3 |     -   -                 | 21  2 4 3 1    #(0 0 2) 3 |     -     -               | 22  1 4 3 2    #(0 0 1) 3 |     -   -                 | 23  3 4 1 2    #(0 0 0) 3 |     -     -               | 24  2 4 1 3 ***#(0 1 2) 3 | 

Asterisks and + signs are marks for myself which mean I know how to find these stages. (it first permutes the sub-sequence of length of 2, then of length of 3 and so on). Minus signs stand between the elements being swapped:

ABCD - - CBAD 

for example.

Kind thanks in advance!

EDIT: It looks like my problem has to do with Levi-Civata symbol

EDIT2: If you were looking for implementation, here's something I could come up with: http://pastebin.com/jszrQV1V

  • 1
    In graph-theoretic terms, you have$a$graph with one vertex for each ordering of your symbols, and an edge between two vertices if you can get from the one ordering to the other by one transposition, and you want$a$hamiltonian path in the graph, a path that visits each vertex exactly once. The graph is called a permutohedron. See http://en.wikipedia.org/wiki/Permutohedron where there's a link to an algorithm for getting the Hamiltonian cycle you want. Heck, I may write this up as an answer.2012-05-18

1 Answers 1

2

According to http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm, "The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of n elements. Each permutation in the sequence that it generates differs from the previous permutation by swapping two adjacent elements of the sequence." I'm not going to copy out the details --- it's all there at the Wikipedia page.

  • 0
    Yes, this is exactly what I was looking for. Thanks a lot!2012-05-18