我正在尋找一個函式，它可以從一個總和為數字的串列中找到所有獨特的組合。我不能對該串列的所有排列組合進行處理，因為這些串列將非常長，而且時間非常緊迫。
the_list = [7,6,5,5,4,3,2,1] 。 stop_sum = 11
因此，如果找到組合（7，3，1），我不希望（1，3，7）被找到。
目前，我正在用一個遞回函式來做這件事，就像下面所說的那樣，但是當串列中包含300多個數字時，這還不夠。(所有的整數)。
the_list = [7,6,5, 5,4,3,2,1]
stop_sum = 11 ]
unique_combos = []
def combo_find(C, S, B=[]/span>)。
for i, a in enumerate（C）。
if a > S:
繼續: 繼續
B.append(a) # B [a]仍然可以是一個可能的串列。
if a == S: # 找到一個可以使用的序列。
sequence = sorted(tuple(B))
if sequence not in unique_combos:
unique_combos.append(sequence)
combo_find(C[i 1:], S - a, B)
B.pop() # 從可能的串列中洗掉[a]。
the_list.sort()
combo_find(the_list, stop_sum)
print(unique_combos)
有誰知道如何以更聰明/更快速的方式完成這個任務？
uj5u.com熱心網友回復：
在使用一些快取的情況下，以下內容應該具有合理的性能：
from functools import lru_cache
def combo_find(C, S) 。
C.sort()
。
def rec(pool, s) 。
if not s:
return [[]] 。
if s < 0:
return []
i, result = 0, [] 。
while i < len（pool）。
crnt = pool[i]
for combo in rec(pool[i 1:], s-crnt) 。
result.append([crnt] combo)
# 使用連續等號中的第一個或沒有！
# 這樣可以避免重復，但允許使用所有的出現，而無需任何成員測驗。
while i < len(pool) and pool[i] == crnt:
i =1
return result
return rec(tuple(C), S) # tuplify，所以args是可哈希的。
combo_find([7,6,5,5, 4,3,2,1】, 11)
[[1, 2, 3, 5], [1, 3, 7], [1, 4, 6], [[1, >5, 5], [2, 3, 6], [2, 4, 5], [4, 7], [5, 6] ]
uj5u.com熱心網友回復：
你可以把solve寫成一個關于你的數字n的函式，以及一個查詢和q。這個演算法不需要對n進行排序，如果你把排序作為一個要求，可以對其進行優化。該演算法是使用歸納推理法撰寫的 -
- 如果查詢的總和為0，那么查詢的結果為0。
- 如果查詢總和
q為零，我們已經知道了答案。產生空解{}，并回傳。 - （歸納）
q不是零。如果q是負數，或者n沒有剩余的數字可以檢查，那么解就出界了或者無法達到。回傳。 - (歸納)
q是正數，并且n有至少一個數字需要檢查。對于子問題的每個解決方案，如果第一個n不存在于解決方案中，則添加它，然后產生。此外，試圖通過跳過第一個n來解決同一個查詢q。
def solve（n, q）。
# 1. 找到解決方案，回傳空集。
if q == 0: return (yield set()
# 2.解決方案出界或沒有更多的數字可以檢查。
if q < 0 or not n。return return
# 3. 對于子問題的每個解決方案，如果第一個n不在解決方案中，則將其添加。
for sln in solve(n[1:], q - n[0] ）。)
if n[0] not in sln。
yield {n[0], *sln}。
# 3.并解決q跳過第一個n的問題。
yield from solve(n[1:], q)
the_list = [7,6, 5, 5,4,3,2, 1]
for x in solve(the_list, 11) 。
print(x)
{4, 7} 。
{1, 3, 7}。
{5, 6}.
{5, 6}{6}。
{1, 4, 6}。
{2, 3, 6}.
{2, 4, 5}。
{1, 2, 3, 5}.
{2, 4, 5}。
{1, 2, 3, 5}。
n可以是任何順序 -
the_list = [2,1, 5, 3]
for x in solve(the_list, 8)。
print(x)
{1, 2, 5}.
{3, 5}。
如果不能找到解決方案，你將得到一個空的結果 -
print(list)solve([1, 2,3], 99）)
[] 。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/309265.html
標籤：
上一篇：使用bloc和freezed庫創建無線電組的初始狀態
下一篇：<p>我想應用一個函式，它一次使用兩列和一行，就像下面的例子所示</p><p>我想應用一個函式。 <preclass="lang-rs-code-b