Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
A comment rather than an answer because it doesn't answer everything - the symbol $(a\:b)$ means the transposition of $a$ and $b$, so its the permutation that swaps $a$ and $b$ and fixes everything else. The dots are then in fact function composition (which can also be thought of as multiplication in the permutation group). In this article you should read the functions left to right, so do the leftmost one first and proceed to the right. –  Matt Pressland May 17 '12 at 15:11
    
Sorry for being a bore - I'm a programmer, so "read from left to right" doesn't tell me much :( do you mean they are left-associative? I.e. f1(f2(f3(x))) rather than f3(f2(f1(x))) given the original expression is f1 . f2 . f3 x? –  wvxvw May 17 '12 at 15:18
    
Yes, that's right (I've not heard that called left-associative before). –  Matt Pressland May 17 '12 at 15:40
    
In Fortran and offspring languages where they decided to add infix operators "for readability" this refers to the order of expression evaluation. For example, assignment is right-associative, but pretty much everything else is left-associative... sigh. But do the numbers in the article mean "swap second and third" or do they mean "swap two and three, regardless of where they are"? I'm trying both ways, but can't build a working model :( –  wvxvw May 17 '12 at 15:51
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 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. –  Gerry Myerson May 18 '12 at 6:35
show 7 more comments

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Yes, this is exactly what I was looking for. Thanks a lot! –  wvxvw May 18 '12 at 9:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.