Algoritmo para encontrar permutación multiset dada el índice lexicográfico

Estoy tratando de encontrar un algoritmo eficiente para encontrar la permutación de un multiset, dado un índice.

Ej: dado {1, 3, 3} . Todas las permutaciones en un orden lexicográfico ascendente son {133, 313, 331} . Estos elementos se indexan como {0, 1, 2} . Dado el index=2 , el resultado es 331.

Encontré un algoritmo para encontrar la permutación de un conjunto dado un índice lexicográfico. Su algoritmo es eficiente: O (n ^ 2).

Sin embargo, el algoritmo se prueba en un conjunto adecuado (por ejemplo, {1, 2, 3} ) y no es correcto en mi prueba. Describo el código de su python aquí para que pueda seguirlo fácilmente.

 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 

 # 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") 

Parece funcionar como se espera

 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 

Complejidad del tiempo: O(n^2) .