当前位置: 首页 > 面试题库 >

快速独特的组合(来自具有重复项的列表),无需查找

范鸿
2023-03-14
问题内容

我似乎尽管有很多在线算法和函数可以从唯一项目列表中生成任意大小的唯一组合,但对于一系列非唯一项目(即包含重复项的列表),则没有可用的算法和函数。具有相同的价值。)

问题是如何在生成器函数中即时生成非唯一列表中的所有唯一组合,而又无需计算出昂贵的过滤出重复项的方法?

现在,由于有一个针对这个问题的奖励动机,因此更容易提供关于我期望实现的目标的清晰性:

首先,让我们提供说明如何检查组合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 ++代码。


问题答案:

目前,最初由50个代表的赏识而不是由100个代表的赏识所启发(而不是完全用C编写的Python扩展模块):

一种有效的算法和实现,(set + combinations)在最佳(和平均)情况下优于显而易见的方法,在最坏的情况下具有竞争力。

似乎有可能使用一种“先做后假”的方法来满足此要求。当前的最新技术是有两种生成器函数算法可用于解决在非唯一列表的情况下获得唯一组合的问题。下面提供的算法将这两种方法结合在一起,这是有可能的,因为它似乎存在一个列表中唯一项百分比的阈值,可用于两种算法之间的适当切换。唯一性百分比的计算只需很少的计算时间,由于所采用时序的共同变化,它甚至无法清楚地显示在最终结果中。

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()一个(由于在列表中唯一元素的数量阈值为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.


 类似资料:
  • 我想要一个列表,它是列表元素列表的组合,例如:我的输入 输出应该是 非常感谢您的帮助。

  • 问题内容: 我从一维数组生成有效的成对组合之后。如果n> 1000,Itertools效率太低 最近的事情在这里。 问题答案: 一种方法是获取内存,从而提高性能- 另一个基于NumPy的控件将用于获取网格视图,然后进行遮罩- 二。三联体组合 我们将扩展相同的方法,以使自己成为三元组合- 高阶组合将同样扩展。 样品运行- 时间(包括Python的内置- )-

  • 下面是适当的方法签名的样子: (问题领域是扑克;列举奥马哈扑克牌中所有可能的板卡组合。是的,还有其他方法可以解决这个问题,但我正在测试这个方法,因为处理比特比大多数其他选择要快得多。)

  • 在尝试检查按钮时,我尝试使用类进行检查,但在运行测试时它会抛出一个错误: “OpenQA.Selenium”类型的异常。WebDriver中发生了InvalidSelectorException。dll,但未在用户代码中处理 附加信息:无效选择器:不允许复合类名 下面是我正在检查元素的类:

  • 问题内容: 是通过其他方式或查询来查找具有特定列而不是如下所示的数据库表名称的方法, 问题答案: 在SQL Server中,您可以查询。 就像是: 如果您有多个模式中的表,则可能需要其他查找来解析模式名称。

  • 首先,我的问题类似于这个已经回答过的问题,在Java中,将两个arrayList合并成一个新的arrayList,没有重复项,并且顺序正确。 然而,这里的不同之处在于,我尝试将两个列表合并在一起,而不仅仅是一个字符串。我的意图是合并以下类型的两个对象(为了简化,我从示例中去掉了不必要的信息): 所以我得到了一个新的项目,它有一个总结计数。这将消除不需要的重复,因为这些对象上的uniqueKey是相