number to unique permutation mapping of a sequence containing duplicates

Question

I am looking for an algorithm that can map a number to a unique permutation of a sequence. I have found out about Lehmer codes and the factorial number system thanks to a similar question, Fast permutation -> number -> permutation mapping algorithms, but that question doesn't deal with the case where there are duplicate elements in the sequence.

For example, take the sequence 'AAABBC'. There are 6! = 720 ways that could be arranged, but I believe there are only 6! / (3! * 2! * 1!) = 60 unique permutation of this sequence. How can I map a number to a permutation in these cases?

Edit: changed the term 'set' to 'sequence'.

Answer 1

From Permutation to Number:

Let K be the number of character classes (example: AAABBC has three character classes)

Let N[K] be the number of elements in each character class. (example: for AAABBC, we have N[K]=[3,2,1], and let N= sum(N[K])

Every legal permutation of the sequence then uniquely corresponds to a path in an incomplete K-way tree.

The unique number of the permutation then corresponds to the index of the tree-node in a post-order traversal of the K-ary tree terminal nodes.

Luckily, we don't actually have to perform the tree traversal -- we just need to know how many terminal nodes in the tree are lexicographically less than our node. This is very easy to compute, as at any node in the tree, the number terminal nodes below the current node is equal to the number of permutations using the unused elements in the sequence, which has a closed form solution that is a simple multiplication of factorials.

So given our 6 original letters, and the first element of our permutation is a 'B', we determine that there will be 5!/3!1!1! = 20 elements that started with 'A', so our permutation number has to be greater than 20. Had our first letter been a 'C', we could have calculated it as 5!/2!2!1! (not A) + 5!/3!1!1! (not B) = 30+ 20, or alternatively as 60 (total) - 5!/3!2!0! (C) = 50

Using this, we can take a permutation (e.g. 'BAABCA') and perform the following computations: Permuation #= (5!/2!2!1!) ('B') + 0('A') + 0('A')+ 3!/1!1!1! ('B') + 2!/1!

= 30 + 3 +2 = 35

Checking that this works: CBBAAA corresponds to

(5!/2!2!1! (not A) + 5!/3!1!1! (not B)) 'C'+ 4!/2!2!0! (not A) 'B' + 3!/2!1!0! (not A) 'B' = (30 + 20) +6 + 3 = 59

Likewise, AAABBC = 0 ('A') + 0 'A' + '0' A' + 0 'B' + 0 'B' + 0 'C = 0

Sample implementation:

import math
import copy
from operator import mul

def computePermutationNumber(inPerm, inCharClasses):
    permutation=copy.copy(inPerm)
    charClasses=copy.copy(inCharClasses)

    n=len(permutation)
    permNumber=0
    for i,x in enumerate(permutation):
        for j in xrange(x):
            if( charClasses[j]>0):
                charClasses[j]-=1
                permNumber+=multiFactorial(n-i-1, charClasses)
                charClasses[j]+=1
        if charClasses[x]>0:
            charClasses[x]-=1
    return permNumber

def multiFactorial(n, charClasses):
    val= math.factorial(n)/ reduce(mul, (map(lambda x: math.factorial(x), charClasses)))
    return val

From Number to Permutation: This process can be done in reverse, though I'm not sure how efficiently: Given a permutation number, and the alphabet that it was generated from, recursively subtract the largest number of nodes less than or equal to the remaining permutation number.

E.g. Given a permutation number of 59, we first can subtract 30 + 20 = 50 ('C') leaving 9. Then we can subtract 'B' (6) and a second 'B'(3), re-generating our original permutation.