c++ - 无需查找的快速独特组合(来自重复列表)

Question

尽管在线有大量算法和函数可用于从唯一项列表生成任意大小的唯一组合，但在非唯一项列表(即包含重复项的列表)的情况下没有可用的算法和函数值相同。)

The question is how to generate ON-THE-FLY in a generator function all the unique combinations from a non-unique list without the computational expensive need of filtering out duplicates?

如果没有其他组合 comboB 两个组合的排序列表相同，我认为组合 comboA 是唯一的。让我们举一个代码检查这种唯一性的例子:

comboA = [1,2,2]
comboB = [2,1,2]
print("B is a duplicate of A" if sorted(comboA)==sorted(comboB) else "A is unique compared to B")

在上面给出的示例中，B 是 A 的拷贝，而 print() 打印出 B 是 A 的拷贝。

获得能够在非唯一列表的情况下即时提供唯一组合的生成器函数的问题在这里得到解决:Getting unique combinations from a non-unique list of items, FASTER? ，但提供的生成器函数需要查找并需要内存，这在大量组合的情况下会导致问题。

在当前版本的答案中，提供的功能无需任何查找即可完成工作，并且看起来是正确的答案，但是......

摆脱查找背后的目标是在列表重复的情况下加快生成唯一组合。

我最初(写这个问题的第一个版本)错误地假设不需要创建用于确保唯一性所需的查找的集合的代码有望比需要查找的代码更具优势。 事实并非如此。至少并非总是如此。到目前为止提供的答案中的代码不使用查找，但在没有冗余列表或列表中只有少数冗余项的情况下需要更多时间来生成所有组合。

这里有一些时间来说明当前的情况:

-----------------
 k: 6 len(ls): 48
Combos   Used Code                               Time
---------------------------------------------------------
12271512 len(list(combinations(ls,k)))       :  2.036 seconds
12271512 len(list(subbags(ls,k)))            : 50.540 seconds
12271512 len(list(uniqueCombinations(ls,k))) :  8.174 seconds
12271512 len(set(combinations(sorted(ls),k))):  7.233 seconds
---------------------------------------------------------
12271512 len(list(combinations(ls,k)))       :  2.030 seconds
       1 len(list(subbags(ls,k)))            :  0.001 seconds
       1 len(list(uniqueCombinations(ls,k))) :  3.619 seconds
       1 len(set(combinations(sorted(ls),k))):  2.592 seconds

以上时间说明了两个极端:没有重复和只有重复。所有其他时间都在这两者之间。

我对以上结果的解释是，纯 Python 函数(不使用任何 C 编译模块)可以非常快，但也可能慢得多，具体取决于列表中有多少重复项。因此，可能没有办法为 Python .so 扩展模块编写 C/C++ 代码以提供所需的功能。

Answer 1

您可以预处理输入列表，而不是对输出进行后处理/过滤。这样，您可以首先避免生成重复项。预处理涉及对输入进行排序(或使用 collections.Counter)。一种可能的递归实现是:

def subbags(bag, k):
    a = sorted(bag)
    n = len(a)
    sub = []

    def index_of_next_unique_item(i):
        j = i + 1

        while j < n and a[j] == a[i]:
            j += 1

        return j

    def combinate(i):
        if len(sub) == k:
            yield tuple(sub)
        elif n - i >= k - len(sub):
            sub.append(a[i])
            yield from combinate(i + 1)
            sub.pop()
            yield from combinate(index_of_next_unique_item(i))

    yield from combinate(0)

bag = [1, 2, 3, 1, 2, 1]
k = 3
i = -1

print(sorted(bag), k)
print('---')

for i, subbag in enumerate(subbags(bag, k)):
    print(subbag)

print('---')
print(i + 1)

输出:

[1, 1, 1, 2, 2, 3] 3
---
(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 2, 2)
(1, 2, 3)
(2, 2, 3)
---
6

递归需要一些堆栈空间，但是这种 + 对输入进行排序应该比生成和丢弃重复使用更少的时间和内存。