Fast permutation -> number -> permutation mapping algorithms

user_87583 0
Viewed 45365

I have n elements. For the sake of an example, let's say, 7 elements, 1234567. I know there are 7! = 5040 permutations possible of these 7 elements.

I want a fast algorithm comprising two functions:

f(number) maps a number between 0 and 5039 to a unique permutation, and

f'(permutation) maps the permutation back to the number that it was generated from.

I don't care about the correspondence between number and permutation, providing each permutation has its own unique number.

So, for instance, I might have functions where

f(0) = '1234567'
f'('1234567') = 0

The fastest algorithm that comes to mind is to enumerate all permutations and create a lookup table in both directions, so that, once the tables are created, f(0) would be O(1) and f('1234567') would be a lookup on a string. However, this is memory hungry, particularly when n becomes large.

Can anyone propose another algorithm that would work quickly and without the memory disadvantage?

permutation combinatorics math algorithm
13 Answers

I had this exact question and thought I would provide my Python solution. It's O(n^2).

import copy

def permute(string, num):
    ''' generates a permutation '''
    def build_s(factoradic): # Build string from factoradic in list form
        string0 = copy.copy(string)
        n = []
        for i in range(len(factoradic)):
            n.append(string0[factoradic[i]])
            del string0[factoradic[i]]
        return n

    f = len(string)
    factoradic = []
    while(f != 0): # Generate factoradic number list
        factoradic.append(num % f)
        num = (num - factoradic[-1])//f
        f -= 1

    return build_s(factoradic)

s = set()
# Print 120 permutations of this string
for i in range(120):
    m = permute(list('abcde'), i)
    s.add(''.join(m))

print(len(s)) # Check that we have 120 unique permutations

It's pretty straight forward; after generating the factoradic representation of the number, I just pick and remove the characters from the string. Deleting from the string is why this is a O(n^2) solution.

Antoine's solution is better for performance.

user_14068880
user_94806890

A related question is computing the inverse permutation, a permutation which will restore permuted vectors to original order when only the permutation array is known. Here is the O(n) code (in PHP):

// Compute the inverse of a permutation
function GetInvPerm($Perm)
    {
    $n=count($Perm);
    $InvPerm=[];
    for ($i=0; $i<$n; ++$i)
        $InvPerm[$Perm[$i]]=$i;
    return $InvPerm;
    } // GetInvPerm

David Spector Springtime Software

user_21843080
Related