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

问题描述 投票：0回答：3

一个例子最能说明这一点

从 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)
python-3.x recursion combinations combinatorics
3个回答
3
投票

给定一种将集合的所有分区创建为大小相等且没有“剩余”/较小容器的方法，您可以轻松编写一个函数来获取具有剩余的所有分区，方法是首先迭代所有组合“剩余”大小并将其附加到其他元素的每个分区。

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

1
投票

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

这是另一种方法，仅在递归函数中使用基本情况（小于或等于您所采用的数字的元素）的测试：

>>> def select_path(L,k):
...  from itertools import combinations
...  if len(L)<=k:
...   yield [tuple(L)] # tuple will match combination type
...   return
...  for c in combinations(L,2):
...   for tail in select_path([i for i in L if i not in c],k):
...     yield [c]+tail
...
>>> [[''.join(t) for t in l] for l in select_path(list('abcde'),2)]
[
['ab', 'cd', 'e'], ['ab', 'ce', 'd'], ['ab', 'de', 'c'], ['ac', 'bd', 'e'], 
['ac', 'be', 'd'], ['ac', 'de', 'b'], ['ad', 'bc', 'e'], ['ad', 'be', 'c'], 
['ad', 'ce', 'b'], ['ae', 'bc', 'd'], ['ae', 'bd', 'c'], ['ae', 'cd', 'b'], 
['bc', 'ad', 'e'], ['bc', 'ae', 'd'], ['bc', 'de', 'a'], ['bd', 'ac', 'e'], 
['bd', 'ae', 'c'], ['bd', 'ce', 'a'], ['be', 'ac', 'd'], ['be', 'ad', 'c'], 
['be', 'cd', 'a'], ['cd', 'ab', 'e'], ['cd', 'ae', 'b'], ['cd', 'be', 'a'], 
['ce', 'ab', 'd'], ['ce', 'ad', 'b'], ['ce', 'bd', 'a'], ['de', 'ab', 'c'], 
['de', 'ac', 'b'], ['de', 'bc', 'a']]
最新问题
© www.soinside.com 2019 - 2025. All rights reserved.