快速独特的组合（来自具有重复项的列表），无需查找

快速独特的组合（来自具有重复项的列表），无需查找

目前，最初由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   2Combos: 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 100Combos: 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  56Combos: 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  64Combos: 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.