Finding n-th permutation without computing others

Question 1

Given an array of N elements representing the permutation atoms, is there an algorithm like that:

function getNthPermutation( $atoms, $permutation_index, $size )

where $atoms is the array of elements, $permutation_index is the index of the permutation and $size is the size of the permutation.

For instance:

$atoms = array( 'A', 'B', 'C' );
// getting third permutation of 2 elements
$perm = getNthPermutation( $atoms, 3, 2 );

echo implode( ', ', $perm )."n";

Would print:

B, A

Without computing every permutation until $permutation_index ?

I heard something about factoradic permutations, but every implementation i've found gives as result a permutation with the same size of V, which is not my case.

Thanks.

Question 2

As stated by RickyBobby, when considering the lexicographical order of permutations, you should use the factorial decomposition at your advantage.

From a practical point of view, this is how I see it:

Perform a sort of Euclidian division, except you do it with factorial numbers, starting with (n-1)!, (n-2)!, and so on.
Keep the quotients in an array. The i-th quotient should be a number between 0 and n-i-1 inclusive, where i goes from 0 to n-1.
This array is your permutation. The problem is that each quotient does not care for previous values, so you need to adjust them. More explicitly, you need to increment every value as many times as there are previous values that are lower or equal.

The following C code should give you an idea of how this works (n is the number of entries, and i is the index of the permutation):

/**
 * @param n The number of entries
 * @param i The index of the permutation
 */
void ithPermutation(const int n, int i)
{
   int j, k = 0;
   int *fact = (int *)calloc(n, sizeof(int));
   int *perm = (int *)calloc(n, sizeof(int));

   // compute factorial numbers
   fact[k] = 1;
   while (++k < n)
      fact[k] = fact[k - 1] * k;

   // compute factorial code
   for (k = 0; k < n; ++k)
   {
      perm[k] = i / fact[n - 1 - k];
      i = i % fact[n - 1 - k];
   }

   // readjust values to obtain the permutation
   // start from the end and check if preceding values are lower
   for (k = n - 1; k > 0; --k)
      for (j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;

   // print permutation
   for (k = 0; k < n; ++k)
      printf("%d ", perm[k]);
   printf("n");

   free(fact);
   free(perm);
}

For example, ithPermutation(10, 3628799) prints, as expected, the last permutation of ten elements:

9 8 7 6 5 4 3 2 1 0

Question 3

To describe a permutation of n elements, you see that for the position that the first element ends up at, you have n possibilities, so you can describe this with a number between 0 and n-1. For the position that the next element ends up at, you have n-1 remaining possibilities, so you can describe this with a number between 0 and n-2.
Et cetera until you have n numbers.

As an example for n = 5, consider the permutation that brings abcde to caebd.

a, the first element, ends up at the second position, so we assign it index 1.
b ends up at the fourth position, which would be index 3, but it's the third remaining one, so we assign it 2.
c ends up at the first remaining position, which is always 0.
d ends up at the last remaining position, which (out of only two remaining positions) is 1.
e ends up at the only remaining position, indexed at 0.

So we have the index sequence {1, 2, 0, 1, 0}.

Now you know that for instance in a binary number, 'xyz' means z + 2y + 4x. For a decimal number,
it's z + 10y + 100x. Each digit is multiplied by some weight, and the results are summed. The obvious pattern in the weight is of course that the weight is w = b^k, with b the base of the number and k the index of the digit. (I will always count digits from the right and starting at index 0 for the rightmost digit. Likewise when I talk about the 'first' digit I mean the rightmost.)

The reason why the weights for digits follow this pattern is that the highest number that can be represented by the digits from 0 to k must be exactly 1 lower than the lowest number that can be represented by only using digit k+1. In binary, 0111 must be one lower than 1000. In decimal, 099999 must be one lower than 100000.

Encoding to variable-base
The spacing between subsequent numbers being exactly 1 is the important rule. Realising this, we can represent our index sequence by a variable-base number. The base for each digit is the amount of different possibilities for that digit. For decimal each digit has 10 possibilities, for our system the rightmost digit would have 1 possibility and the leftmost will have n possibilities. But since the rightmost digit (the last number in our sequence) is always 0, we leave it out. That means we're left with bases 2 to n. In general, the k'th digit will have base b[k] = k + 2. The highest value allowed for digit k is h[k] = b[k] - 1 = k + 1.

Our rule about the weights w[k] of digits requires that the sum of h[i] * w[i], where i goes from i = 0 to i = k, is equal to 1 * w[k+1]. Stated recurrently, w[k+1] = w[k] + h[k] * w[k] = w[k]*(h[k] + 1). The first weight w[0] should always be 1. Starting from there, we have the following values:

k    h[k] w[k]    

0    1    1  
1    2    2    
2    3    6    
3    4    24   
...  ...  ...
n-1  n    n!

(The general relation w[k-1] = k! is easily proved by induction.)

The number we get from converting our sequence will then be the sum of s[k] * w[k], with k running from 0 to n-1. Here s[k] is the k'th (rightmost, starting at 0) element of the sequence. As an example, take our {1, 2, 0, 1, 0}, with the rightmost element stripped off as mentioned before: {1, 2, 0, 1}. Our sum is 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37.

Note that if we take the maximum position for every index, we'd have {4, 3, 2, 1, 0}, and that converts to 119. Since the weights in our number encoding were chosen so that we don't skip any numbers, all numbers 0 to 119 are valid. There are precisely 120 of these, which is n! for n = 5 in our example, precisely the number of different permutations. So you can see our encoded numbers completely specify all possible permutations.

Decoding from variable-base
Decoding is similar to converting to binary or decimal. The common algorithm is this:

int number = 42;
int base = 2;
int[] bits = new int[n];

for (int k = 0; k < bits.Length; k++)
{
    bits[k] = number % base;
    number = number / base;
}

For our variable-base number:

int n = 5;
int number = 37;

int[] sequence = new int[n - 1];
int base = 2;

for (int k = 0; k < sequence.Length; k++)
{
    sequence[k] = number % base;
    number = number / base;

    base++; // b[k+1] = b[k] + 1
}

This correctly decodes our 37 back to {1, 2, 0, 1} (sequence would be {1, 0, 2, 1} in this code example, but whatever ... as long as you index appropriately). We just need to add 0 at the right end (remember the last element always has only one possibility for its new position) to get back our original sequence {1, 2, 0, 1, 0}.

Permuting a list using an index sequence
You can use the below algorithm to permute a list according to a specific index sequence. It's an O(n²) algorithm, unfortunately.

int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];

for (int i = 0; i < n; i++)
{
    int s = sequence[i];
    int remainingPosition = 0;
    int index;

    // Find the s'th position in the permuted list that has not been set yet.
    for (index = 0; index < n; index++)
    {
        if (!set[index])
        {
            if (remainingPosition == s)
                break;

            remainingPosition++;
        }
    }

    permuted[index] = list[i];
    set[index] = true;
}

Common representation of permutations
Normally you would not represent a permutation as unintuitively as we've done, but simply by the absolute position of each element after the permutation is applied. Our example {1, 2, 0, 1, 0} for abcde to caebd is normally represented by {1, 3, 0, 4, 2}. Each index from 0 to 4 (or in general, 0 to n-1) occurs exactly once in this representation.

Applying a permutation in this form is easy:

int[] permutation = new int[] { 1, 3, 0, 4, 2 };

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

for (int i = 0; i < n; i++)
{
    permuted[permutation[i]] = list[i];
}

Inverting it is very similar:

for (int i = 0; i < n; i++)
{
    list[i] = permuted[permutation[i]];
}

Converting from our representation to the common representation
Note that if we take our algorithm to permute a list using our index sequence, and apply it to the identity permutation {0, 1, 2, ..., n-1}, we get the inverse permutation, represented in the common form. ({2, 0, 4, 1, 3} in our example).

To get the non-inverted premutation, we apply the permutation algorithm I just showed:

int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];

for (int i = 0; i < n; i++)
{
    normal[identity[i]] = list[i];
}

Or you can just apply the permutation directly, by using the inverse permutation algorithm:

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

int[] inverted = { 2, 0, 4, 1, 3 };

for (int i = 0; i < n; i++)
{
    permuted[i] = list[inverted[i]];
}

Note that all the algorithms for dealing with permutations in the common form are O(n), while applying a permutation in our form is O(n²). If you need to apply a permutation several times, first convert it to the common representation.

Question 4

You probably cannot get the i'th digit of the k'th permutation of n elements in O(n) time or space, because representing the number k itself requires O(log(n!)) = O(n log n) bits, and any manipulations with it have corresponding time complexity.

Question 5

If repetition is allowed, then:

the first permutation is 0000000000
the second permutation is 0000000001
the tenth permutation is 0000000009
the hundredth permutation is 0000000099
the thousandth permutation is 0000000999
the millionth permutation is 0000999999

and so on.

All of these are simply the number n-1 padded with enough number of zeroes on the left to make the whole string of length 10.

So to get the actual nth combination, all you would have to do is (below snippet in Python, you can convert to Java easily):

>>> def find_nth_combination(n):
...     print "0" * (10-len(str(n-1))) + str(n-1)
... 
>>> find_nth_combination(1)
0000000000
>>> find_nth_combination(100)
0000000099
>>> find_nth_combination(9062300000)
9062299999
>>> find_nth_combination(12300000)
0012299999

In case you want to solve this with repetition, you can have a look here (code is in Python).

To get all permutations, simply go through all the numbers.

So, you will need to do something like:

for x in xrange(1, 1001):
    find_nth_combination(x)

which will output:

Question 6

I'll just give the outline of a solution for each:

Given a permutation of a list of integers {1,2,...,N}, how can I tell what is the index of that permutation in lexicographic ordering?

To do this, ask yourself how many permutations start with 1? There are (N - 1)!. Now, let's do an example:

3 1 2

How many permutations of 1 2 3 start with 1 or 2? 2*2!. This one has to be after those, so its index is at least 2*2! = 4. Now check the next element. How many permutations of 1 2 start with 0? None. You're done, the index is 4. You can add 1 if you want to use 1-based indexing.

Given a number k, how can I calculate k-th permutation of numbers {1,2...,N}?

Given 4, how can we get 3 1 2? We have to find each element.

What can we have on the first position? If we have 1, the maximum index can be 2! - 1 = 1 (I'm using zero-based indexing). If we have 2, the maximum can be 2*2! - 1 = 3. If we have 3, the maximum can be 5. So we must have 3:

Now, we have reduced the problem to finding the 4 - 2*2! = 0-th permutation of 1 2, which is 1 2 (you can reason about it recursively as above).

Finding n-th permutation without computing others

Answers

php,algorithm,math,permutation