python - 给定词典索引查找多集排列的算法

Question

我正在尝试找到一种有效的算法来找到给定索引的多重集的排列。

例如:给定 {1, 3, 3}。所有按升序排列的字典顺序都是 {133, 313, 331}。这些元素被索引为 {0, 1, 2}。给定 index=2，结果为 331。

I found an algorithm找到给定词典索引的集合的排列。他的算法是高效的:O(n^2)。

但是，该算法是在适当的集合(例如 {1, 2, 3})上测试的，在我的测试中并不正确。我在这里描述了他的 python 代码，以便您可以轻松理解。

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

似乎按预期工作

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

时间复杂度:O(n^2)。