查找所有可能的子集总和给定的数
问题描述:
我正在学习Python,我有一个问题,这似乎是一个简单的任务。查找所有可能的子集总和给定的数
我想查找所有可能的总和给定数字的数字组合。
例如:4 - > [1,1,1,1] [1,1,2] [2,2] [1,3]
我挑选生成所有可能子集的解决方案(2^n),然后产生那些总和等于数量的那些。我的病情有问题。代码:
def allSum(number):
#mask = [0] * number
for i in xrange(2**number):
subSet = []
for j in xrange(number):
#if :
subSet.append(j)
if sum(subSet) == number:
yield subSet
for i in allSum(4):
print i
顺便说一句,这是一个好方法?
答
下面是一些代码,我几年前看到的伎俩:
>>> def partitions(n):
if n:
for subpart in partitions(n-1):
yield [1] + subpart
if subpart and (len(subpart) < 2 or subpart[1] > subpart[0]):
yield [subpart[0] + 1] + subpart[1:]
else:
yield []
>>> print list(partitions(4))
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]
其他参考:
答
该解决方案不起作用,对吧?它永远不会多次向一个子集添加一个数字,所以你永远不会得到,例如[1,1,2]。它永远不会跳过一个数字,所以你永远不会得到,例如,[1,3]。
所以你的解决方案的问题是双重的:一,你实际上并没有产生1..number范围内的所有可能的子集。二,所有子集的集合将排除你应该包括的东西,因为它不允许一个数字出现多次。
这种问题可以概括为搜索问题。想象一下,您想要尝试的数字是树上的节点,然后您可以使用深度优先搜索来查找树中代表解决方案的所有路径。这是一棵无限大的树,但幸运的是,你永远不需要搜索全部。
答
下面是其中的工作方式是采取全1的列表,并递归地通过添加后续元素折叠它的另一种方法,这应该不是生成所有可能的子集是更有效的:
def allSum(number):
def _collapse(lst):
yield lst
while len(lst) > 1:
lst = lst[:-2] + [lst[-2] + lst[-1]]
for prefix in _collapse(lst[:-1]):
if not prefix or prefix[-1] <= lst[-1]:
yield prefix + [lst[-1]]
return list(_collapse([1] * number))
>>> allSum(4)
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]
>>> allSum(5)
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [1, 1, 3], [2, 3], [1, 4], [5]]
可以剥去最后一个值,如果你不想要这个微不足道的情况。如果您只是循环播放结果,请删除list
调用,然后返回发生器。
答
这相当于this question中描述的问题,可以使用类似的解决方案。
要阐述:
def allSum(number):
for solution in possibilites(range(1, number+1), number):
expanded = []
for value, qty in zip(range(1, number+1), solution):
expanded.extend([value]*qty)
yield expanded
这转化这个问题到了这个问题,然后再返回。
仅供参考,这些被称为[分区](http://en.wikipedia.org/wiki/Partition_%28number_theory%29) – interjay
为什么不从所需的数字开始,并减去数字? – Marcin
我认为这可以通过使用DP(Dinamic编程)更高效地完成,否则你会得到一个令人讨厌的复杂性。 – juliomalegria