Finding n-th permutation without computing others

Question

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.

Answer 1

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