如何找到组中所有可能的子组

Question

假设我们有组1、2、3，因此可能的子组是：

    {1,2,3}
    {1} {2,3}
    {1,2} {3}
    {1,3} {2}
    {1} {2} {3}

你明白了。在

我必须用递归来做。到目前为止我所拥有的（不起作用），而且有点不同。 这个想法是你有一个代表立方体的整数的列表（用来建造一座塔），并且你想要建造尽可能多的具有一定高度的塔。假设你得到了 立方体[5,2,6,6,1,1,4]，你想要的高度是7，那么最好的构建是[5,2] [6,1] [6,1] [4]。在

代码：

^{pr2}$

但我只得到[5,2] [6,1]。有什么想法吗？在

Answer 1

你的主要问题是你没有重复你没有使用的值，例如： 先拿5，2 比6,6，但不好，所以你跳过，然后取6,1 但你再也不会拿前6个了，再得到一个6，1的连击。 这就是为什么你必须重复所有的值后，你选择一个组合。在

代码（可能更好，用你的逻辑）：

    def find_tower(blocks, height):

def solve(groups, cur_group, index):
    if sum(cur_group) == height:
        new_group = list(groups)# if tower is on right height
        new_group.append(cur_group)# add to groups of towers
        return solve(new_group, [], 0)
    if index == len(blocks):# if index max
        return groups
    elif sum(cur_group) > height:# if its higher than height
        return groups
    elif blocks[index] is None:# if its a None index skip
        return solve(groups, cur_group, index+1)

    temp = blocks[index]
    blocks[index] = None# changing used value to none
    r1 = solve(groups, cur_group + [temp], index+1)
    blocks[index] = temp# puttin back used value
    r2 = solve(groups, cur_group, index+1)
    return max(r1, r2, key=lambda x: len(x))# return longer group
return solve([], [], 0)

Answer 2

我并不是说下面的方法是有效的，但它为您提供了一个如何递归构建结果的想法：

import itertools

def partitions(items, n):
    if n == 1:
        return [set([e]) for e in items]
    results = partitions(items, n - 1)
    for i, j in itertools.combinations(range(len(results)), 2):
        newresult = results[i] | results[j]
        if newresult not in results:
            results.append(newresult)
    return results


items = [1,2,3]
print partitions(items, len(items))
# [set([1]), set([2]), set([3]), set([1, 2]), set([1, 3]), set([2, 3]), set([1, 2, 3])]

Answer 3

这里有一个使用递归的简单方法。其思想是，对于由x和其他一些元素xs组成的列表，子集集是xs的所有子集，再加上x的子集。在

from copy import *

def all_subsets(xs):
  if not xs:
    return [[]]
  else:
    x = xs.pop()
    subsets = all_subsets(xs)
    subsets_copy = deepcopy(subsets) # NB you need to use a deep copy here!
    for s in subsets_copy:
      s.append(x)
    subsets.extend(subsets_copy)
    return subsets