如何递归检查列表python的所有组合

Question

我正在尝试编写代码来递归检查一个列表是否可以分成两个具有相同总和的子列表，因此需要传递列表的所有组合，例如：[1,2,3,4] 所以我需要检查：

1------2,3,4

1,2------3,4

1,3------2,4

等等.... 但我找不到方法。

Answer 1

暴力破解：

import itertools

seq = [1, 2, 3, 4]
S = sum(seq)
for i in xrange(1, len(seq)):
    for c in itertools.combinations(seq, i):
        print c, 2*sum(c) == S

不过，这不是解决问题的最有效方法。读这个：http://en.wikipedia.org/wiki/Partition_problem

Answer 2

您可以使用

simleo 建议的 itertools。这是蛮力解决方案，将运行指数时间。
给定 here 使用传统的子集问题解决方案，其中运行s 在 (total_sum_of_nums)*len(list) 时间

Answer 3

recursively check if a list could be divided to two sublists with the same sum

您可以使用递归轻松实现 greedy partition algorithm：

def _greedy_part(r, sa, la, sb, lb):
    if not r:
        return sa == sb, la, lb;

    if sb < sa:
        # swap both lists in order to always have
        # the "lower sum list" as sa/la
        sb, sa = sa, sb
        lb, la = la, lb

    return _greedy_part(r[1:], sa+r[0], la+r[0:1], sb, lb)

def greedy_part(r):
    return _greedy_part(sorted(r,reverse=True), 0, [], 0, [])

关键思想是始终将最大剩余值添加到总和最小的列表中。再一次，该解决方案在 Python 中表现不佳，因为函数调用效率不高并且 Python 没有 tail call optimization.

鉴于样本测试：

print(greedy_part([1,2,3,4]))
print(greedy_part([1,2,3,4,5]))
print(greedy_part([6,1,2,3]))

它将产生：

(True, [4, 1], [3, 2])
(False, [5, 2, 1], [4, 3])
(True, [3, 2, 1], [6])

如何递归检查列表python的所有组合

How to recursively check all combinations of list python

python

recursion

backtracking