一個例子最能說明
從 N 個唯一項的串列開始 = ['A','B','C','D','E']
選擇 k=2 項
在這里，我們有 Python 實作來顯示可能的組合數量：
combos = [c for c in combinations(['A','B','C','D','E'],2)]
combos = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E')]
現在，對于這 10 種組合中的每一種，想象從 N 的原始串列中取出該集合，并重新計算選擇剩余 Nk 項的方法的數量。
取第一組 ('A', 'B') 給我們留下 ['C','D','E'] 的 N 項
combos = [c for c in combinations(['C','D','E'],2)]
combos = [('C', 'D'), ('C', 'E'), ('D', 'E')]
再次，我們對 3 個組合中的每一個重復上述程序，依次將每個組合從當前串列中移開，最終在這種情況下僅在串列中留下一個專案，這可以做出一個簡單的最終決定，無需任何組合擴展。
所以回顧一下，我一直稱之為選擇路徑：首先我們選擇（'A'，'B'）然后我們選擇（'C'，'D'）。最后我們選擇了（'E'）
所以解決方案路徑是一個串列 [('A', 'B'), ('C', 'D'), ('E')] 并且遞回已經到達底部，并終止該分支，因為有串列中沒有更多專案。
如果我們第一次選擇 ('A', 'C')，則遞回在頂部重新開始，然后繼續擴展選項，創建一個新的選擇路徑分支。
最終結果應該是所有可能的選擇路徑的串列。這將是一個元組串列的串列，因為解決方案路徑本身就是一個選擇串列。
Final Result should resemble:
[
[('A', 'B'), ('C', 'D'), ('E')],
[('A', 'C'), ('B', 'D'), ('E')],
[('A', 'D'), ('B', 'C'), ('E')],
...
[('D', 'E'), ('A', 'B'), ('C')],
[('D', 'E'), ('A', 'C'), ('B')],
...
]
顯然，這只是一個例子，我想擴大它并改變 N 和 K。
My first attempt at coding in python has not been very successfull. I can't seem to understand what my function should return each recursion and how to manage the lists between the levels of recursion. I'm really in need of help here.
def get_combo_path(prod_list, phase, k):
from itertools import combinations
from collections import defaultdict
import copy
prod_list=copy.deepcopy(prod_list) #Worried about pointers, not sure I need this
phase=copy.deepcopy(phase) #Worried about pointers, not sure I need this
prod_combos = [c for c in combinations(prod_list,k)]
print('prod_list',prod_list)
for x in prod_combos:
phase.append(x) #Store which combo we are selecting
prods_left = list(set(prod_list)-set(x)) #Subtract the set from the list
print('x',x) #Troubleshooting
print('phase',phase) #Troubleshooting
print('prods_left',prods_left) #Troubleshooting
get_combo_path(prods_left, phase, k) #Recursively call func for each combo
print() #Troubleshooting
return None #What should I return?
#Now to run the function
from collections import defaultdict
prod_list = [chr(ord('a') p).upper() for p in range(0,5)] #Makes initial list of chars
new_groups = get_combo_path(prod_list, [], 2)
uj5u.com熱心網友回復：
給定一種將集合的所有磁區創建為沒有“剩余”/較小的 bin 的相等大小的 bin 的方法，您可以通過首先迭代所有組合來輕松撰寫一個函式來獲取所有剩余的磁區“剩余”大小并將其附加到其他元素的每個磁區。
使用Gareth Rees 的答案中的 set partitions 函式，您可以這樣做：
def partitions(s, r):
s = set(s)
assert (len(s) % r == 0)
if len(s) == 0:
yield ()
return
first = next(iter(s))
rest = s.difference((first,))
for c in itertools.combinations(rest, r - 1):
first_subset = (first,) c
for p in partitions(rest.difference(c), r):
yield (first_subset,) p
def get_combo_path(prod_list, k):
"""Given distinct elements prod_list, give all partitions into
bins of size k with possibly 1 remainder bin"""
prod_set = set(prod_list)
n = len(prod_set)
remainder = n % k
if remainder == 0:
yield from partitions(prod_set, k)
return
for left_overs in itertools.combinations(prod_set, remainder):
rest = prod_set.difference(left_overs)
for p in partitions(rest, k):
yield p (left_overs,)
for combo in get_combo_path(['A','B','C','D','E'], 2):
print(combo)
這使：
(('E', 'D'), ('C', 'B'), ('A',))
(('E', 'C'), ('D', 'B'), ('A',))
(('E', 'B'), ('D', 'C'), ('A',))
(('E', 'D'), ('A', 'B'), ('C',))
(('E', 'A'), ('D', 'B'), ('C',))
(('E', 'B'), ('D', 'A'), ('C',))
(('D', 'A'), ('C', 'E'), ('B',))
(('D', 'C'), ('A', 'E'), ('B',))
(('D', 'E'), ('A', 'C'), ('B',))
(('D', 'A'), ('C', 'B'), ('E',))
(('D', 'C'), ('A', 'B'), ('E',))
(('D', 'B'), ('A', 'C'), ('E',))
(('E', 'A'), ('C', 'B'), ('D',))
(('E', 'C'), ('A', 'B'), ('D',))
(('E', 'B'), ('A', 'C'), ('D',))
請注意，這需要不同的元素。如果你想允許重復，你會做同樣的事情，但傳遞range(len(prod_list))而不是prod_list，并使用生成的磁區來保存prod_list.
uj5u.com熱心網友回復：
對@kcsquared 解決方案稍作修改，以便考慮組的選擇順序。
這里的關鍵是組本身是組合，因此分組中的順序無關緊要，但分組的順序確實很重要。例如，在我隨機給一行人提供主菜和配菜組合的場景中，盤子上食物的順序無關緊要，但你在該行的哪個位置可能決定你是否有雞肉或牛肉。
def partitions(s, r):
s = set(s)
assert (len(s) % r == 0)
if len(s) == 0:
yield ()
return
for c in itertools.combinations(s, r):
first_subset = c
for p in partitions(s.difference(c), r):
yield (first_subset,) p
def get_combo_path(prod_list, k):
"""Given distinct elements prod_list, give all partitions into
bins of size k with possibly 1 remainder bin"""
prod_set = set(prod_list)
n = len(prod_set)
remainder = n % k
if remainder == 0:
yield from partitions(prod_set, k)
return
for left_overs in itertools.combinations(prod_set, remainder):
rest = prod_set.difference(left_overs)
for p in partitions(rest, k):
yield p (left_overs,)
結果（將其與原始答案進行比較以查看是否有更多行）
(('E', 'B'), ('D', 'A'), ('C',))
(('E', 'D'), ('B', 'A'), ('C',))
(('E', 'A'), ('D', 'B'), ('C',))
(('B', 'D'), ('E', 'A'), ('C',))
(('B', 'A'), ('E', 'D'), ('C',))
(('D', 'A'), ('E', 'B'), ('C',))
(('C', 'E'), ('B', 'A'), ('D',))
(('C', 'B'), ('E', 'A'), ('D',))
(('C', 'A'), ('E', 'B'), ('D',))
(('E', 'B'), ('C', 'A'), ('D',))
(('E', 'A'), ('C', 'B'), ('D',))
(('B', 'A'), ('C', 'E'), ('D',))
(('C', 'B'), ('D', 'A'), ('E',))
(('C', 'D'), ('B', 'A'), ('E',))
(('C', 'A'), ('D', 'B'), ('E',))
(('B', 'D'), ('C', 'A'), ('E',))
(('B', 'A'), ('C', 'D'), ('E',))
(('D', 'A'), ('C', 'B'), ('E',))
(('C', 'E'), ('D', 'A'), ('B',))
(('C', 'D'), ('E', 'A'), ('B',))
(('C', 'A'), ('E', 'D'), ('B',))
(('E', 'D'), ('C', 'A'), ('B',))
(('E', 'A'), ('C', 'D'), ('B',))
(('D', 'A'), ('C', 'E'), ('B',))
(('C', 'E'), ('D', 'B'), ('A',))
(('C', 'B'), ('E', 'D'), ('A',))
(('C', 'D'), ('E', 'B'), ('A',))
(('E', 'B'), ('C', 'D'), ('A',))
(('E', 'D'), ('C', 'B'), ('A',))
(('B', 'D'), ('C', 'E'), ('A',))
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/439498.html
標籤：python-3.x recursion combinations combinatorics