Algorithm for finding multiset permutation given lexicographic index
Question: I am trying to find an efficient algorithm to find permutation of a multiset,
given an index.

Ex: given `{1, 3, 3}`. All permutations in an ascending lexicographic order
are `{133, 313, 331}`. These elements are indexed as `{0, 1, 2}`. Given
`index=2`, the result is 331.

[I found an algorithm](http://stackoverflow.com/questions/8940470/algorithm-
for-finding-numerical-permutation-given-lexicographic-index) to find
permutation of a set given a lexicographic index. His algorithm is efficient:
O(n^2).

However, the algorithm is tested on a proper set (e.g. `{1, 2, 3}`), and not
correct on my test. I describe his python code here so that you can easily
follow.

    
    
    from math import factorial, floor #// python library
    from math import factorial, floor #// python library
    i=5 #// i is the lexicographic index (counting starts from 0)
    n=3 #// n is the length of the permutation
    p = range(1,n+1) #// p is a list from 1 to n
    for k in range(1,n+1): #// k goes from 1 to n
        d = i//factorial(n-k) #// use integer division (like division+floor)
        print(p[d]),
        p.remove(p[d])   #//delete p[d] from p
        i = i % factorial(n-k) #// reduce i to its remainder
    


Answer: 
    # Python 2
    from collections import Counter
    from math import factorial
    
    
    def count_permutations(counter):
        values = counter.values()
        return (
            factorial(sum(values))/reduce(lambda a, v: a * factorial(v), values, 1)
        )
    
    
    def permutation(l, index):
        l = sorted(l)
    
        if not index:
            return l
    
        counter = Counter(l)
        total_count = count_permutations(counter)
        acc = 0
        for i, v in enumerate(l):
    
            if i > 0 and v == l[i-1]:
                continue
    
            count = total_count * counter[v] / len(l)
    
            if acc + count > index:
                return [v] + permutation(l[:i] + l[i + 1:], index - acc)
    
            acc += count
    
        raise ValueError("Not enough permutations")
    

Seems to work as expected

    
    
    In [17]: for x in range(50): print x, permutation([1, 1, 2, 2, 2], x)
    0 [1, 1, 2, 2, 2]
    1 [1, 2, 1, 2, 2]
    2 [1, 2, 2, 1, 2]
    3 [1, 2, 2, 2, 1]
    4 [2, 1, 1, 2, 2]
    5 [2, 1, 2, 1, 2]
    6 [2, 1, 2, 2, 1]
    7 [2, 2, 1, 1, 2]
    8 [2, 2, 1, 2, 1]
    9 [2, 2, 2, 1, 1]
    10---------------------------------------------------------------------------
    ValueError                                Traceback (most recent call last)
    [...]
    ValueError: Not enough permutations
    

Time complexity: `O(n^2)`.

