# Adjacent transposition - explain in layman terms

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
- -


for example.

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

-
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. – Matthew 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). – Matthew 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
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