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:
- ABCD - swap A and B because
- BACD - swap B and C because
- 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