Decomposition of numbered permutations.

[KingNothing]

Say I have three elements: A, B, C. I can list all the permutations by going alphabetical in the first element, then the second, then the third, and so on, like so:

1. ABC
2. ACB
3. BAC
4. BCA
5. CAB
6. CBA

What I'm wondering, is given a number N, how do I decompose this into knowing what permutation it specifies?

For example, how do I figure that N=5 corresponds to CAB?
Is there a better order to list them in which makes this problem simpler?

 

[awkward]

See

http://en.wikipedia.org/wiki/Factorial_number_system

especially the information on the Lehmer code

 

[KingNothing]

Thanks awkward for the information. I actually had seen that already, but dismissed it on the basis that I figured using FNS would be too computationally intensive. That is, I would have to first convert the decimal representation to a FNS representation, then convert the FNS representation into a permutation.

Wikipedia speaks of processing the FNS digit-by-digit, removing items from a lexicographically-sorted list as part of this process. I think in my case that may be a deal breaker, but I'm not sure.

Are you aware of any algorithms that decompose a decimal representation (does not need to be lexicographical order, that was just my example) without the use of lists or FNS?

 

[Yuqing]

The following should be suited to a recursive algorithm and uses your numbering scheme.

The first element can be given as \left\lceil\frac{x}{(N-1)!}\right\rceil where \left\lceil\right\rceil is the ceiling function, x is the index number and N is the total number of elements in the list. The second element can be obtained recursively by applying the same formula to the list obtained by removing the first element and with a new index of r which is the remainder of x when divided by (N-1)! (with 0 taken as (N-1)!)

As an example taking your ordering of the set {A, B, C}

1. ABC
2. ACB
3. BAC
4. BCA
5. CAB
6. CBA

notice that if we remove the first element, say C, then

AB
BA

is the same ordering applied to the set {A, B}. The same can be generalized into larger sets. For a 4 element set, say {A, B, C, D} let's try to apply our method. Say we want element number 22, then the first element is given by \left\lceil\frac{22}{6}\right\rceil = 4 which is the fourth element of our set, namely D. Now applying the same method to the set with D removed, that is {A, B, C} with new index 4. Applying the same method we obtain that the second element is \left\lceil\frac{4}{2}\right\rceil = 2 which is B. The remainder of division is 0, so we take it to be 2! = 2 instead. This is repeated a third time with the set {A, C} to yield a third element of C and final element of A.

 

[KingNothing]

Yuqing - let me see if I have this right. I'm going to rewrite it slightly using integer division (floor(x/y)) and modulus. A foreslash (/) will indicate integer division, and a % will indicate modulus. N will be the number of elements in the "available list". The lists will have a zero-based index. ":=" is the assignment operator.

We start with an ABCD list, and the index x=22.
22/(4-1)! = 3 -> D, so D is first element.
List becomes ABC. N:=3. x:=22%4=4.

4/(3-1)! = 2 -> C, so C is second element.
List becomes AB. N:=2. x:=2%(3-1)!=0.

0/(2-1)! = 0 -> A, so A is third element.
List becomes B. N:=1. x:=0%(2-1)!=0.

----------------

Ideally I would only compute the first denominator, and in each step divide it by N after N is decremented. One challenge is that list element removal and re-indexing is very non-trivial in a computer. I wonder if there might be a way mathematically to prevent an element from being selected from the list, without having to remove it.

0/(1-1)! = 0 -> B, so B is fourth element.
List becomes empty, and we are done.

 

[Yuqing]

Yuqing - let me see if I have this right. I'm going to rewrite it slightly using integer division (floor(x/y)) and modulus. A foreslash (/) will indicate integer division, and a % will indicate modulus. N will be the number of elements in the "available list". The lists will have a zero-based index. ":=" is the assignment operator.

We start with an ABCD list, and the index x=22.
22/(4-1)! = 3 -> D, so D is first element.
List becomes ABC. N:=3. x:=22%4=4.

4/(3-1)! = 2 -> C, so C is second element.
List becomes AB. N:=2. x:=2%(3-1)!=0.

0/(2-1)! = 0 -> A, so A is third element.
List becomes B. N:=1. x:=0%(2-1)!=0.

----------------

Ideally I would only compute the first denominator, and in each step divide it by N after N is decremented. One challenge is that list element removal and re-indexing is very non-trivial in a computer. I wonder if there might be a way mathematically to prevent an element from being selected from the list, without having to remove it.

0/(1-1)! = 0 -> B, so B is fourth element.
List becomes empty, and we are done.

The algorithm is more or less correct, but you have to make some adjustments for when x/(N-1)! is integer. In the second step above, the element chosen is supposed to be B and not C and this is a remnant of shifting the index and flooring the argument. I think subtracting one from the the case when x/(N-1)! should take care of it.

As for the list problem, I am a bit unsure. I myself am not a programmer, while I can write code I doubt it will be efficient enough for your purposes. I suppose you can keep an alternate list of indices which should not be selected, but again I'm unsure whether this is anymore efficient than simply reindexing.