Multipositional permutation search algorithm with lexicographic index

Question

I am trying to find an efficient algorithm for finding a permutation of a multiset based on an index.

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

I found an algorithm to find the permutation of the set given by the lexicographic index. Its algorithm is efficient: O (n ^ 2).

However, the algorithm is tested on the correct set (for example, {1, 2, 3} ) and does not match my test. Here I describe his python code so 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(nk) #// use integer division (like division+floor) print(p[d]), p.remove(p[d]) #//delete p[d] from p i = i % factorial(nk) #// reduce i to its remainder 

Answer 1

 # 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 

Difficulty of time: O(n^2) .