FAST獨特的組合（從重複列表中）

Question

我認爲，儘管網上有大量的算法和函數用於從唯一項目列表中生成任意大小的唯一組合，但是沒有可用的的非唯一項的列表的情況下（即，包含相同的值的重複列表。）

的問題是如何產生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的副本和打印（）打印真。

獲取發生器功能時能夠在非唯一列表的情況下即時提供唯一組合的問題在此解決：Getting unique combinations from a non-unique list of items, FASTER?，但提供的發生器功能需要查找並需要存儲器大量的組合。

中回答中提供的功能的最新版本做這項工作沒有任何查詢，似乎這裏是正確的答案，但...

背後擺脫查找的目標是加快代在重複列表的情況下的唯一組合。

我最初（寫這個問題的第一個版本）錯誤地認爲，不需要創建用於查找所需的集合以確保唯一性的代碼，預計會比需要查找的代碼帶來優勢。 情況並非如此。至少不總是。到目前爲止提供的答案中的代碼不使用查找，但是在沒有冗餘列表的情況下或者只有少數多餘的項目在列表中時，需要花費更多的時間來生成所有組合。

這裏是一些定時來說明目前的狀況：

----------------- 
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++代碼提供所需的功能。

Answer 1

而不是後處理/過濾您的輸出，您可以預處理您的輸入列表。這樣，您可以避免首先生成重複項。預處理包括對輸入進行排序（或使用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 

需要用於遞歸一些堆棧空間，但這種排序+輸入應該使用基本上更少的時間+存儲器不是生成和廢棄重複。

Answer 2

當前狀態的最先進的最初的啓發由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％，基於uniqueCombinations()發生器是 上(set + combinations)不惡化明顯的優勢 函數在相反的情況下它得到比iterUniqueCombos()更快一個（由於(set + combinations)，並在60％的閾值在列表中的變體(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.