Finding N-Th Permutation Without Computing Others

// See https://stackoverflow.com/a/7919887/5459839function getPermutationByRank(n, rank) {    // Sageguard for inaccurate calculations: rank <= 9007199254740991    if (rank > Number.MAX_SAFE_INTEGER) throw "Too large rank for JavaScript";    var perm = (function loop(i, fact) {        // Calculate factorials and subtract from rank from highest to lowest        return i > n ? [] :               [loop(i+1, fact * i).concat(Math.floor(rank / fact) % n),                rank = rank % fact][0];    })(1, 1);    // Readjust values to obtain the permutation    // start from the end and check if preceding values are lower    for (let k = n - 1; k > 0; --k)      for (let j = k - 1; j >= 0; --j)         if (perm[j] <= perm[k])            perm[k]++;    return perm;}
// See https://stackoverflow.com/a/1622539/5459839:function nextPermutation(perm) {    // Find longest non-increasing suffix    var i = perm.length - 2;    while (i >= 0 && perm[i] >= perm[i + 1])        i--;    // Now i is the head index of the suffix        // Are we at the last permutation already?    if (i < 0) return; // no more permuations        // Let perm[i] be the pivot    // Find rightmost element that exceeds the pivot    var j = perm.length - 1;    while (perm[j] <= perm[i])        j--;    // Now the value perm[j] will become the new pivot    // Assertion: j >= i        // Swap the pivot with j    [perm[i], perm[j]] = [perm[j], perm[i]];        // Reverse the suffix    j = perm.length - 1;    i++;    while (i < j) {        [perm[i], perm[j]] = [perm[j], perm[i]];        i++;        j--;    }    return perm;}
// Create a generator using above two functions:function* generatePermutationsFrom(n, rank) {    var perm = getPermutationByRank(n, rank);
    yield perm;    while (nextPermutation(perm)) {        yield perm;    }}
// Utility functions for OP specific requirementsfunction deciSecondsSince(dt) {    return Math.floor((Date.now() - dt.getTime())/100);}
function permToString(perm) {    var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';    return perm.map ( v => chars[v] ).join('');}
var deciSecs = deciSecondsSince(new Date('2000-01-01')); // ~5293000000 var iter = generatePermutationsFrom(36, deciSecs);
// Output next permuation every decisecond:document.body.textContent = permToString(iter.next().value);setInterval(function () {    document.body.textContent = permToString(iter.next().value);}, 100);

body { font-family: monospace }

How can I calculate n-th permutation (or tell the lexicographic order of a given permutation)?

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:

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).

How to get nth permutation when repetition is allowed?

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:

0000000000
0000000001
...
...
0000000997
0000000998
0000000999

Finding nth permutation for parallelized C/C++

I've posted the following example elsewhere, but let me repeat it here:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>

typedef char           element_t;
typedef unsigned long  permutation_t;

static permutation_t factorial(const permutation_t n)
{
    permutation_t i, result = 1;
    for (i = 2; i <= n; i++) {
        const permutation_t  newresult = result * i;
        if ((permutation_t)(newresult / i) != result)
            return 0;
        result = newresult;
    }
    return result;
}

int permutation(element_t *const        buffer,
                const element_t *const  digits,
                const size_t            length,
                permutation_t           index)
{
    permutation_t  scale;
    size_t         i, d;

    if (!buffer || !digits || length < 1)
        return errno = EINVAL;

    scale = factorial(length);
    if (!scale)
        return errno = EMSGSIZE;
    if (index >= scale)
        return errno = ENOENT;

    /* Copy original ordered set to mutable buffer */     
    memmove(buffer, digits, length * sizeof (element_t));

    for (i = 0; i < length - 1; i++) {
        scale /= (permutation_t)(length - i);
        d = index / scale;
        index %= scale;
        if (d > 0) {
            const element_t c = buffer[i + d];
            memmove(buffer + i + 1, buffer + i, d * sizeof (element_t));
            buffer[i] = c;
        }
    }

    return 0;
}

The factorial() function is just a slow but careful implementation of the factorial. Since 13! > 2³², 21! > 2⁶⁴, and 35! > 2¹²⁸, there are only a very few possible results for 32, 64, or 128-bit unsigned integer permutation_t types, it would be better to simply use an array lookup for the factorials instead (as rcgldr already mentioned).

The permutation(buffer, digits, length, index) function takes a target buffer of length length, and fills it with the index'th permutation of digits. (The digits is read-only, immutable.)

This is not the fastest possible implementation, but it will calculate any permutation in O(length) time complexity (ignoring the memmove() operation; O(length²) if you consider the memmove()). It is sub-optimal, because it uses memmove() to reorder the items in the target buffer, and requires two divisions (and one modulus with the same divisor) per element.

Considering the maximum practical length limitations (12, 20, or 34 elements, depending on the size of the permutation_t type), the use of memmove() is not an issue (because the data is within one or at most a couple of cache lines).

This is thread-safe, as long as only one thread operates on the same target buffer at the same time; multiple threads generating different target buffers from the same source digits buffer is thread-safe.

PHP: Alphabetical permutation

Let's take a look at how the permutation function is defined:

def permute(string):
  for each char in string
    sub <- remove char from string
    return concat(char, permute(sub))
end

For a string of length L, the permute function returns an array of length L!. Thus we can see that the list of permutations starting with the char at index i in the string starts at the i*(L-1)! element in the final array.

Thus the find the permutation at index N, we need to iteratively narrow down our search space, by finding the character to append (index given by N / (M - 1)!) and its corresponding substring. We remove this character from the string, append it to the result, and repeat with N <- N % (M - 1)! on the substring (this is the offset index into the list of permutations of this substring).

PHP code:

function factorial($M) {
    $N = 1;
    for (;$M > 0;$M--)
        $N *= $M;
    return $N;
}
function remove_from_str($input, $index) {
   $str1 = substr($input, 0, $index);
   $str2 = substr($input, $index+1);
   return $str1.$str2;
}

function get_permutation($input, $N) {
   $L = strlen($input);
   $result = "";
   for ($M = $L; $M > 0; $M--) {
      $F = factorial($M-1);
      $j = intval(floor($N / $F));
      $result = $result.$input[$j];
      $input = remove_from_str($input, $j);
      $N = $N % $F;
   }
   return $result;
}

Test:

echo get_permutation("ABCDEFGHIJK", 1600000); // Outputs "AFEIGCDJKBH"

(Note: N here starts at 0 rather than 1)

How to find all permutations of an Array of Strings in Ruby without using too much memory?

What you're doing now is creating an enumerator which will yield one permutation at a time, not consuming much memory, then with the .map(&:join) you're putting everything that comes out of this enumerator into one gigantic array searchMap.

Instead of that you should pull one permutation from the enumerator at a time and do your trick on that, instead of iterating over the gigantic array with searchMap.each:

line = gets
L=line.split(" ")

S =  gets

L.permutation do |item|
    if S.include? item.join
        puts S.index(item.join)
    end
end

Getting i'th prefix without computing others

The standard representation of a permutation as a number uses Lehmer codes represented in the factorial number system. The idea is that every permutation of n elements can be mapped to a sequence of n numbers, the first of which is in the range 0 to (n - 1), the second of which is in the range 0 to (n - 2), etc. This sequence of numbers can then be represented as a single integer in the factorial number system.

I believe that it should be possible to adapt this trick to work with prefixes of permutations rather than entire permutations. Suppose that you have n elements and want to choose a permutation of k of them. To do this, start off by computing the Lehmer code for the partial permutation. Instead of getting a sequence of n numbers, you'll get back a sequence of k numbers. For example, given the partial permutation c a d drawn from a b c d e f g, your Lehmer code would be found as follows:

• c is the second (zero-indexed) element of a b c d e f g
• a is the zeroth (zero-indexed) element of a b d e f g
• d is the first (zero-indexed) element of b d e f g

So the Lehmer code would be (2, 0, 1).

Once you have this Lehmer code, you can try to encode it as a single integer. To do this, you can use a modified factorial number system encoding. Specifically, you can try doing the following. If you have n elements and want a permutation of k of them, then there will be a total of (n - k + 1) possible choices for the very last element. There are a total of (n - k + 2) possible choices for the second-to-last element, (n - k + 3) possible choices for the third-to-last element, etc. Consequently, you could take your Lehmer code and do the following:

1. Keep the final digit unchanged.
2. Multiply the second-to-last element by (n - k + 1).
3. Multiply the third-to-last element by (n - k + 1)(n - k + 2)
   4 ...
4. Multiply the first element by (n - k + 1)(n - k + 2)...(n - 1)
5. Sum up these values.

This produces a unique integer code for the permutation.

For example, our Lehmer code was (2, 0, 1), n = 7, and k = 3. Therefore, we'd compute

1 + 0 × (7 - 3 + 1) + 2 × (7 - 3 + 2)(7 - 3 + 3)

= 1 + 2 × (5 × 6)

= 5 + 2 × 30

= 61

To invert this process, you can take the integer and run it backwards through this procedure to recover the partial Lehmer code. To do this, start off by taking the number and dividing by (n - k + 1)(n - k + 2)...(n - 1) to get back the very first digit of the Lehmer code. Then, mod the number by (n - k + 1)(n - k + 2)...(n - 1) to drop off the first digit. Then, divide the number by (n - k + 1)(n - k + 2)...(n - 2) to get back the second digit of the Lehmer code, then mod by (n - k + 1)(n - k + 2)...(n - 2) to drop off the second digit. Repeat this until all the digits of the Lehmer code have been reconstructed.

For example, given prefix 61, n = 7, and k = 3, we would start off by dividing 61 by 7 × 6 = 30. This gives 2, remainder 1. Thus the first digit of the Lehmer code is 2. Modding by 30, we get back the number 1. Next, we divide by 6. This gives 0, remainder 1. Thus the second digit is 0. Finally, we read off the remaining number, which gives the last digit of the Lehmer code, 1. We have recovered our Lehmer code (2, 0, 1), from which we can easily reconstruct the permutation.

Hope this helps!

---

Related Topics