快速独特的组合(来自列表与重复)没有LOOKUPS

Question

我似乎尽管有大量的算法和函数用于从唯一项目列表中生成任何大小的唯一组合,但是在非唯一项目列表(即包含重复项的列表)中没有可用的相同的价值.)

问题是如何在生成器函数中生成ON-THE-FLY所有来自非唯一列表的独特组合,而不需要过滤重复计算的昂贵计算？

现在,由于对这个问题有一个很有动力的答案,因此更容易提供我期望实现的目标:

首先,让我们提供一些代码,说明如何检查组合comboB是否与另一个组合重复(comboA):

comboA = [1,2,2]
comboB = [2,1,2]
print("B is a duplicate of A:", comboA.sort()==comboB.sort())

在给定的例子中,B是A的副本,print()打印为True.

在这里解决了获取能够在非唯一列表的情况下即时提供独特组合的生成器功能的问题:从非唯一项目列表中获取独特的组合,更快？,但是提供的生成器函数需要查找并且需要内存,以便在大量组合的情况下导致问题.

在当前版本的答案提供功能完成工作没有任何查找,似乎是正确的答案,但......

摆脱查找的目的是在列表重复的情况下加速生成唯一组合.

我最初(编写这个问题的第一个版本)错误地认为,不需要创建用于确保唯一性所需的查找集的代码预期会比需要查找的代码具有优势.事实并非如此.至少并非总是如此.截至目前提供的答案中的代码不使用查找,但是如果没有冗余列表或者列表中只有少量冗余项,则需要花费更多时间来生成所有组合.

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

-----------------
 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函数(没有itertools或其他C编译模块)可以非常快,但它也可能慢得多,具体取决于列表中有多少重复项.因此,可能无法为提供所需功能的Python .so扩展模块编写C++代码.

Answer 1

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

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

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