从非唯一的项目列表中获取独特的组合，更快吗？

Question

首先，我能够做到，但我对速度不满意。

我的问题是，有没有更好、更快的方法来做到这一点？

我有一个如下所示的项目列表：

[(1,2), (1,2), (4,3), (7,8)]

我需要获得所有独特的组合。例如，两个项目的独特组合将是：

[(1,2), (1,2)], [(1,2), (4,3)], [(1,2), (7,8)], [(4,3), (7,8)]

使用 itertools.combinations 后，由于重复，我得到的比这多得多。例如，我得到包含 (1,2) 的每个列表两次。如果我创建一组这些组合，我会得到独特的组合。当原始列表有 80 个元组并且我想要其中包含 6 个项目的组合时，问题就出现了。完成该设置需要 30 秒以上。如果我能把这个数字降下来，我会很高兴。

我知道组合的数量很大，这就是为什么创建该组合非常耗时。但我仍然希望有一个库能够以某种方式优化该过程，从而加快速度。

值得注意的是，在我发现的所有组合中，我只测试了前 10000 个左右。因为在某些情况下，所有组合都可能需要处理太多，所以我不想在它们上花费太多时间，因为还有其他测试要做。

这是我现在拥有的示例：

from itertools import combinations

ls = [list of random NON-unique sets (x,y)]
# ls = [(1,2), (1,2), (4,3), (7,8)]  # example
# in the second code snipped it is shown how I generate ls for testing

all_combos = combinations(ls, 6)
all_combos_set = set(all_combos)

for combo in all_combos_set:
  do_some_test_on(combo)

如果您想测试一下..这是我用来测试不同方法速度的方法：

def main3():
    tries = 4
    elements_in_combo = 6
    rng = 90
    data = [0]*rng
    for tr in range(tries):
        for n in range(1, rng):
            quantity = 0
            name = (0,0)
            ls = []
            for i in range(n):
                if quantity == 0:
                    quantity = int(abs(gauss(0, 4)))
                    if quantity != 0:
                        quantity -= 1
                    name = (randint(1000,7000), randint(1000,7000))
                    ls.append(name)
                else:
                    quantity -= 1
                    ls.append(name)

            start_time = time.time()
            all_combos = combinations(ls, elements_in_combo)
            all_combos = set(all_combos)

            duration = time.time() - start_time
            data[n] += duration
            print(n, "random files take", duration, "seconds.")

            if duration > 30:
                break

    for i in range(rng):
        print("average duration for", i, "is", (data[i]/tries), "seconds.")

Answer 1

最初提出的问题是“有更好、更快的方法吗？” 实际上有两个问题：

• 有更快的方法吗？
• 有没有更好的办法？

我想缩小“有更快的方法吗？”这个问题的答案。到：

有没有更快的方法从列表中删除重复项，如下所示：

lstWithUniqueElements = 列表（集（lstWithDuplicates））

？

据我所知，没有更快的方法......

现在让我们更多地关注问题的第二部分（“有更好的方法吗？”）。回答此类问题通常非常困难，需要进行很多讨论，但这里不会出现这种情况，因为更好的方法是什么，问题的作者已经明确指出了（引文）：

我很想使用生成器功能。itertools组合（）本身是一个可迭代的，而不是一个列表或集合，所以如果我弄清楚如何产生独特的组合，那就太好了。

所以这里是：

def uniqueCombinations(lstList, comboSize): 
    from itertools import combinations
    lstList.sort()
    allCombos = combinations(lstList, comboSize)
    setUniqueCombos = set()
    for comboCandidate in allCombos:
        if comboCandidate in setUniqueCombos:
            continue
        yield comboCandidate
        setUniqueCombos.add(comboCandidate)

就是这样 ...

这里也许还有一件事值得一提。问题的作者选择了获取唯一组合的方法，以防它们生成的列表不仅具有唯一性，而且具有相同值的多个元素在某些特殊情况下不起作用，例如：

set(combinations(['a','a','b','a'], 2)) gives: {('a', 'b'), ('b', 'a'), ('a', 'a')}
uniqueCombinations(['a','a','b','a'],2) gives: {('a', 'b'), ('a', 'a')}

在这两者之间，stackoverflow 上有一个纯 Python 函数，它比上面提供的更快或更慢。怎样才能更快和更慢呢？请参阅此处了解详细信息。