From a number that map to a permutation, how to generate other permutations that differ from the previous perm. by swapping of elements?

user_1083855 0
Viewed 931

Using Lehmer code, any permutation of a sequence of N elements can be encoded and mapped to a decimal number using the factorial number system.

Example :

Lehmer codes for ABCD permutations :

ABDC => 0010
CBAD => 2100
DCBA => 3210

These inversions vectors can be converted to a decimal using factorials :

2100 => 2 x 3! + 1 x 2! + 0 x 1! + 0 x 0!
     => 2 x 6  + 1 x 2  + 0 x 1  + 0 x 1
     => 14

So CBAD permutation can be map directly to number 14.

My question is :

From a number that map to a permutation, is there a computationally efficient method to generate numbers of other permutations that differ from the previous permutation by swapping two elements in the sequence ?

Example : We have 4 (which map to ADBC) and we want to swap the first two elements. Result is 18 (or DABC).

4    => 18
0200 => 3000
ADBC => DABC

Method would be declared like this :

swap(4, 0, 1); //return 18

I want to avoid doing the whole process again but reverse :

Number => Factorial => Rebuild original permutation and swap elements (costly) =>
  Factorial => Number

Note : On wikipedia there is article about Steinhaus–Johnson–Trotter algorithm but i'm not sure it would help here.

factorial permutation math algorithm c#
1 Answers

(answer to my own question)

I finally found out. It took me a while but here is final formula :

int swap(int value, int indexA, int indexB)
{
   int valueA = value % factorial(indexA+1) / factorial(indexA);
   int valueB = value % factorial(indexB+1) / factorial(indexB);

   int deltaA = valueB - valueA;
   if (valueB >= valueA) deltaA++;

   int deltaB = valueA - valueB;
   if (valueA > valueB) deltaB--;

   return value + (deltaA * factorial(indexA)) + (deltaB * factorial(indexB));
}

//note: indexes have to be given from right to left
//so to swap elements at 0, 1 for 4 : swap(4, 3, 2);

Some explanation :

as an example, lets take 14. the factorial representation is :

2 x 3! + 1 x 2! + 0 x 1! + 0 x 0!

if we want to swap the first two elements of the sequence (CBAD => BCAD or 2100 => 1100), we need to take 2 and 1 terms in the factorial, and exchange them :

1 x 3! + 2 x 2! + 0 x 1! + 0 x 0!

note: since the factorial expression is just a sum, we do not need to reevaluate the full expression, just to apply some delta :

  1 x 3! + 2 x 2! + 0 x 1! + 0 x 0!

= 2 x 3! + 1 x 2! + 0 x 1! + 0 x 0! - ( 1 x 3!) + ( 1 x 2!)

= 14 - ( 1 x 3!) + ( 1 x 2!)

the extraction of factorial terms is done in the first two lines of code, and delta are applied at the last line.

note: we need to take care since we swapped elements, the indices inside Lehmer code might have changed, and optionally add 1 or remove 1 to terms inside factorial :

=> 14 - ( 1 x 3!) + ( 0 x 2!)

= 14 - 6 = 8

this last part is done in the two "if" conditions in c# code

user_10838550
Related