一个例子说明了它是最好的
从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的原始列表中删除该集合，并重新计算选择剩余N-k个项目的方法的数量。
取第一组("A"，"B"(，我们只剩下N个项目的"C"，"D"，"E"]
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。
我第一次尝试用python进行编码并不是很成功。我似乎不明白我的函数应该在每次递归中返回什么，以及如何管理递归级别之间的列表。我在这里真的需要帮助。
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)
如果有一种方法可以将一个集合的所有分区创建为大小相等的、没有"遗留"/更小的bin的bin，那么您可以很容易地编写一个函数来获得所有具有遗留的分区，方法是先迭代"遗留"大小的所有组合，然后将其附加到其他元素的每个分区。
使用Gareth Rees在这里的答案中的集分区函数，你可以这样做：
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中相应元素的索引。
对@kcsquare解进行轻微修改，以便考虑组的选择顺序。
这里的关键是，分组本身就是组合，因此分组中的顺序并不重要，但分组的顺序确实重要。例如，在一个场景中，我随机给一排人一道主菜和一道配菜，盘子里的食物顺序无关紧要，但你在那一排的位置可能决定你是吃鸡肉还是牛肉。
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',))