Find the N-th permutation of an ordered string (Using factorial number system).

Problem — If all of the permutations of a string are listed alphabetically, we call it lexicographic order. What is the nth lexicographical permutation of a given string?

Instead of finding all permutations and looking up the nth, we can directly calculate the nth permutation. We need to first understand the Factorial Number System (or Factoradic number system) to solve this question. A factorial number system uses factorial values instead of powers of numbers (binary system uses powers of 2, decimal uses powers of 10) to denote place-values (or base).

The place values (base) are -

`5!= 120    4!= 24    3!=6    2!= 2    1!=1    0!=1 etc..`

The digit in the zeroth place is always 0. The digit in the first place (with base = 1!) can be 0 or 1. The digit in the second place (with base 2!) can be 0,1 or 2 and so on. Generally speaking, the digit at nth place can take any value between 0-n.

First few numbers represented as factoradics-

0 -> 0 = 0*0!
1 -> 10 = 1*1! + 0*0!
2 -> 100 = 1*2! + 0*1! + 0*0!
3 -> 110 = 1*2! + 1*1! + 0*0!
4 -> 200 = 2*2! + 0*1! + 0*0!
5 -> 210 = 2*2! + 1*1! + 0*0!
6 -> 1000 = 1*3! + 0*2! + 0*1! + 0*0!
7 -> 1010 = 1*3! + 0*2! + 1*1! + 0*0!
8 -> 1100 = 1*3! + 1*2! + 0*1! + 0*0!
9 -> 1110
10-> 1200

There is a direct relationship between nth lexicographical permutation of a string and its factoradic representation.

For example, here are the permutations of the string “abcd”.

`0  abcd       6  bacd        12  cabd       18  dabc1  abdc       7  badc        13  cadb       19  dacb2  acbd       8  bcad        14  cbad       20  dbac3  acdb       9  bcda        15  cbda       21  dbca4  adbc       10  bdac       16  cdab       22  dcab5  adcb       11  bdca       17  cdba       23  dcba`

We can see a pattern here, if observed carefully. The first letter changes after every 6th (3!) permutation. The second letter changes after 2(2!) permutation. The third letter changed after every (1!) permutation and the fourth letter changes after every (0!) permutation. We can use this relation to directly find the nth permutation.

Once we represent n in factoradic representation, we consider each digit in it and add a character from the given string to the output. If we need to find the 14th permutation of ‘abcd’. 14 in factoradics -> 2100.

Start with the first digit ->2, String is ‘abcd’. Assuming the index starts at 0, take the element at position 2, from the string and add it to the Output.

`Output               String  c                   abd  2                   012`

The next digit -> 1.String is now ‘abd’. Again, pluck the character at position 1 and add it to the Output.

`Output               String cb                    ad 21                    01`

Next digit -> 0. String is ‘ad’. Add the character at position 1 to the Output.

`Output               String cba                    d 210                    0`

Next digit -> 0. String is ‘d’. Add the character at position 0 to the Output.

`Output              String cbad                 '' 2100`

To convert a given number to Factorial Number System,successively divide the number by 1,2,3,4,5 and so on until the quotient becomes zero. The reminders at each step forms the factoradic representation.

For eg, to convert 349 to factoradic,

`Quotient        Reminder        Factorial Representation349/1            349               0                             0349/2            174               1                            10174/3            58                0                           01058/4             14                2                          201014/5             2                 4                         420102/6              0                 2                        242010`

Factoradic representation of 349 is 242010.

Java Code -

Driver code to test the functions in Java -

`Note : The length of factoradic representation should be equal to the length of the character array. Prepend zeros to ensure the length is same.`
Like what you read? Give Aiswarya Prakasan a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.