无需查找，在具有重复项的列表中快速查找唯一组合

Question

无需查找，在具有重复项的列表中快速查找唯一组合

9

尽管有很多算法和函数可以从一组唯一的项目中生成任意大小的独特组合，但对于包含重复值的列表（即包含重复值的列表），没有可用的算法和函数。

问题是如何在生成器函数中即时生成来自非唯一列表的所有独特组合，而无需计算昂贵的去重操作？

如果对于另一个组合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 的副本。

解决非唯一列表情况下提供即时独特组合的生成器函数的问题在这里得到了解决：从一个非唯一项目列表中获取唯一组合，更快？，但提供的生成器函数需要查找并且需要内存，在大量组合的情况下会导致问题。

当前答案版本中提供的函数可以在不进行任何查找的情况下完成工作，并且似乎是正确的答案，但是……

摆脱查找的目标是为了加速在带有重复项的列表情况下生成唯一组合。

我最初（编写这个问题的第一个版本时）错误地假设代码不需要创建用于查找的集合，不需要确保独特性，会比需要查找的代码更有优势。事实并非如此。 至少不总是这样。迄今为止提供的答案中的代码没有使用查找，但在没有冗余列表或仅少量的冗余项目在列表中的情况下，生成所有组合需要更长的时间。

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

-----------------
 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编译模块）可以非常快，但也可能因列表中有多少个重复而变得更慢。因此，可能没有绕过编写C/C++代码来提供所需功能的Python .so扩展模块的方法。

- Claudio

你如何确定 (1,2,2) 和 (2,1,2) 中哪一个是“正确”的？ - John

你的第一条评论正是我在寻找的。 - John

@Claudio 我还发现了这个帖子，其中包含一个_简单得多_的迭代算法（需要对输入进行排序），以及一个递归算法。它们似乎比当前的答案更有效率，但我还没有真正测试过它们。 - user6732794

@lazydog 请看这里 http://cython.org/ 和这里 https://dev59.com/9KHia4cB1Zd3GeqPSl8B，如果您愿意，可以自由提供另一个答案，并使用现成的模块比当前答案中最快的模块更快。从您的回答中得到的递归算法已经生成了一个非常好的C编译Python模块，仅比循环而非递归版本的迭代器类使用该算法进行优化的Cython代码略慢。抱歉 - 我还没有找到更新此主题的最新状态的时间。 - Claudio

2个回答

1

当前的最先进技术最初是基于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()生成器函数在列表具有不到60％唯一元素且不劣于uniqueCombinations()变体的情况下提供了明显的优势，在相反的情况下，它比iterUniqueCombos()更快（由于在列表中唯一元素的数量达到60％阈值时在(set + combinations)和(no lookups)变体之间切换）。

===========  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.

- Claudio

我不确定如何将递归版本重写为等效的迭代版本，但这里有一个替代迭代算法，可能更容易作为C扩展适应。itertools.combinations_with_replacement的源代码可能会有所帮助。不过，我认为你答案中的组合元算法方法更简单有效。它类似于标准的快速排序+插入排序组合。 - user6732794

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user6732794 · Accepted Answer

与其对输出进行后处理/过滤，不如对输入列表进行预处理。这样一来，您就可以避免在第一次生成时产生重复项。预处理涉及对输入进行排序（或使用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

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