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

  • 0
    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.2012-05-17
  • 0
    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?2012-05-17
  • 0
    Yes, that's right (I've not heard that called left-associative before).2012-05-17
  • 0
    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 :(2012-05-17
  • 0
    They mean swap $2$ and $3$, regardless of where they are. In most mathematical contexts you don't think of the numbers as a sequence, but as a set, so they're unordered. The permutation is then a bijection from this set to itself - the transposition $(2\:3)$ maps $2\mapsto 3$, $3\mapsto 2$, and fixes the other elements. It can be useful to visualise this as changing the order of the terms in a sequence however.2012-05-17
  • 0
    I'm afraid of asking something extra silly, but, in that case, what $k < l$ means? Is there a requirement for a symmetric group to define any order? While with numbers it makes sense, with symbols (which you can also permute) - how would I tell if it was {'foo', 'bar'} or {'bar', 'foo'}?2012-05-17
  • 0
    The $k requirement is just to make the notation neat when explaining how to build an arbitrary transposition out of transpositions of adjacent elements. A permutation needn't be thought of as an ordering of the elements, in general it's a bijection from a set to itself. So for {foo,bar} there are two permutations, the identity, and the permutation that maps foo to bar and bar to foo. If you choose an ordering on the elements, you can see the permutation as an ordering in Cauchy's two-line notation; see http://en.wikipedia.org/wiki/Permutation#Notation.2012-05-17
  • 0
    Then I'm starting to suspect I'm not asking the correct question... Does the article I refer to speak about a way to generate *all* permutations for a certain group without repetitions? Because the way it suggests transposing elements doesn't seem to do it - it repeats after 13 transpositions in the group of 4 elements, I triple checked.2012-05-17
  • 0
    You can definitely generate all permutations of a set from the transpositions, and that section tells you that all you actually need are the transpositions of adjacent elements. However, what it seems like you're trying to do is to write down all the permutations in a list, with no repeats, and each one being the composition of the previous one with a transposition, and I don't know if that is possible in general. All I know is that you can get to each permutation by applying transpositions, but then if you want another one you might have to go back and start again.2012-05-17
  • 0
    Certainly there is! That's what my example shows - I kind of "see" the pattern, but I can't code it because it turns out to be overly complex. But thanks a lot for your help so far. That you clarified the article for me was very helpful.2012-05-17
  • 0
    So it definitely works for $4$ objects, and I suppose I don't find it so hard to believe that it will work for all $n$, but I don't actually know why. Glad I was of some help anyway!2012-05-17
  • 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