递归地从 N 中选择 K 项，直到为空

Question

举个例子最能说明问题

从 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')] and递归已触底，并终止此分支，因为列表中没有更多项目。

如果我们第一次选择 ('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 中的第一次编码尝试并不是很成功。我似乎无法理解我的函数应该 return 每次递归以及如何管理递归级别之间的列表。我真的需要帮助。

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)

Answer 1

如果有一种方法可以将一个集合的所有分区创建到 equal-size 个没有 'left-over'/更小的容器的容器中，您可以轻松地编写一个函数来获取具有 left-over 的所有分区，通过首先迭代 'left-over' 大小的所有组合并将它们附加到其他元素的每个分区。

使用 Gareth Rees' answer here 中的设置分区功能，您可以这样做：

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 中相应元素的索引。

Answer 2

对@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',))

递归地从 N 中选择 K 项，直到为空

Recursively choose K items from N , until empty

recursion

combinations

combinatorics

python-3.x