首页 文章

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

提问于
浏览 次
10

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

问题是如何在生成器函数中生成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是A的副本，print（）打印 True .

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

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

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

我最初（编写这个问题的第一个版本）错误地认为，不需要创建用于确保唯一性所需的查找集的代码可以提供优于需要查找的代码的优势 . It is not the case. 至少并非总是如此 . 到目前为止提供的答案中的代码不使用查找，但是如果没有冗余列表或者列表中只有少量冗余项，则需要花费更多时间来生成所有组合 .

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

-----------------
 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代码 .

c++ python-3.x unique combinations lookup

2 回答

  • 4

    您可以预处理输入列表，而不是对输出进行后处理/过滤 . 这样，您可以避免首先生成重复项 . 预处理涉及对输入进行排序（或使用 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

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

    回复于
  • 2

    目前最先进的技术灵感来自50个而不是100个代表的奖励（而不是完全用C语言编写的Python扩展模块）：

    在最佳（和平均）情况下，优于明显（设置组合）方法的有效算法和实现，并且在最坏的情况下与其竞争 .

    似乎有可能使用一种“在你做它之前伪造它”的方法来满足这个要求 . 当前最先进的技术是有两种生成器函数算法可用于解决在非唯一列表的情况下获得唯一组合的问题 . 下面提供的算法将它们两者结合起来，因为它似乎存在列表中唯一项的百分比的阈值，该阈值可用于两种算法之间的适当切换 . 独特性百分比的计算是在如此微小的计算时间内完成的，由于所采用的时间的共同变化，它甚至不能在最终结果中清楚地显示出来 .

    def iterFastUniqueCombos(lstList, comboSize, percUniqueThresh=60):

    lstListSorted = sorted(lstList)
    lenListSorted = len(lstListSorted)

    percUnique = 100.0 - 100.0*(lenListSorted-len(set(lstListSorted)))/lenListSorted

    lstComboCandidate = []
    setUniqueCombos = set()

    def idxNextUnique(idxItemOfList):
        idxNextUniqueCandidate = idxItemOfList + 1
        while (
                idxNextUniqueCandidate < lenListSorted 
                    and 
                lstListSorted[idxNextUniqueCandidate] == lstListSorted[idxItemOfList]
        ): # while
            idxNextUniqueCandidate += 1
        idxNextUnique = idxNextUniqueCandidate
        return idxNextUnique

    def combinate(idxItemOfList):
        if len(lstComboCandidate) == sizeOfCombo:
            yield tuple(lstComboCandidate)
        elif lenListSorted - idxItemOfList >= sizeOfCombo - len(lstComboCandidate):
            lstComboCandidate.append(lstListSorted[idxItemOfList])
            yield from combinate(idxItemOfList + 1)
            lstComboCandidate.pop()
            yield from combinate(idxNextUnique(idxItemOfList))

    if percUnique > percUniqueThresh:
        from itertools import combinations
        allCombos = combinations(lstListSorted, comboSize)
        for comboCandidate in allCombos:
            if comboCandidate in setUniqueCombos:
                continue
            yield comboCandidate
            setUniqueCombos.add(comboCandidate)
    else:
        yield from combinate(0)
    #:if/else    
#:def iterFastUniqueCombos()

    下面提供的时序表明，上面的 iterFastUniqueCombos() 生成器功能提供了明显优于 uniqueCombinations() 变体的优势，如果列表中的独特元素少于60％，并且在相反的情况下基于 (set + combinations) 的 uniqueCombinations() 生成器函数不会变得更糟比 iterUniqueCombos() 更快（由于 (set + combinations) 和 (no lookups) 变体在列表中的唯一元素数量的60％阈值之间切换）：

    ===========  sizeOfCombo: 6   sizeOfList: 48   noOfUniqueInList 1   percUnique   2
Combos: 12271512  print(len(list(combinations(lst,k))))           :   2.04968 seconds.
Combos:        1  print(len(list(      iterUniqueCombos(lst,k)))) :   0.00011 seconds.
Combos:        1  print(len(list(  iterFastUniqueCombos(lst,k)))) :   0.00008 seconds.
Combos:        1  print(len(list(    uniqueCombinations(lst,k)))) :   3.61812 seconds.

==========  sizeOfCombo: 6   sizeOfList: 48   noOfUniqueInList 48   percUnique 100
Combos: 12271512  print(len(list(combinations(lst,k))))           :   1.99383 seconds.
Combos: 12271512  print(len(list(      iterUniqueCombos(lst,k)))) :  49.72461 seconds.
Combos: 12271512  print(len(list(  iterFastUniqueCombos(lst,k)))) :   8.07997 seconds.
Combos: 12271512  print(len(list(    uniqueCombinations(lst,k)))) :   8.11974 seconds.

==========  sizeOfCombo: 6   sizeOfList: 48   noOfUniqueInList 27   percUnique  56
Combos: 12271512  print(len(list(combinations(lst,k))))           :   2.02774 seconds.
Combos:   534704  print(len(list(      iterUniqueCombos(lst,k)))) :   1.60052 seconds.
Combos:   534704  print(len(list(  iterFastUniqueCombos(lst,k)))) :   1.62002 seconds.
Combos:   534704  print(len(list(    uniqueCombinations(lst,k)))) :   3.41156 seconds.

==========  sizeOfCombo: 6   sizeOfList: 48   noOfUniqueInList 31   percUnique  64
Combos: 12271512  print(len(list(combinations(lst,k))))           :   2.03539 seconds.
Combos:  1114062  print(len(list(      iterUniqueCombos(lst,k)))) :   3.49330 seconds.
Combos:  1114062  print(len(list(  iterFastUniqueCombos(lst,k)))) :   3.64474 seconds.
Combos:  1114062  print(len(list(    uniqueCombinations(lst,k)))) :   3.61857 seconds.
    回复于

相关问题