具有相同总和的子集-python

本文介绍了具有相同总和的子集-python的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

这里我有一个数字数组，如何确定数组是否可以分为两个子集，两个子集中的元素之和是相同的，如果这些子集可用，则程序应返回true.

here i have an array of numbers, how to determine whether array can be divided into two subsets for which the sum of elements in both subsets is the same, if the subsets are available, the program should return true.

For array = [8, 6, 3, 5], the output should be sub(array) = true

推荐答案

这是一种蛮力解决方案.它使用 Itertools食谱中的powerset食谱在文档中生成所有子集.然后，它使用 itertools.groupby对它们进行汇总和分组. .最后，它检查所有具有相同总和的子集对，以找到不相交的对.

Here's a brute-force solution. It uses the powerset recipe from the Itertools Recipes in the docs to generate all the subsets. It then sorts and groups them by sum, using itertools.groupby. Then finally it checks all pairs of subsets with the same sum to find pairs that do not intersect.

from itertools import chain, combinations, groupby

def equal_sum_partitions(seq):
    subsets = chain.from_iterable(combinations(seq, r) for r in range(len(seq)+1))
    for k, g in groupby(sorted(subsets, key=sum), key=sum):
        group = [set(u) for u in g]
        if len(group) > 1:
            for u, v in combinations(group, 2):
                if not u & v:
                    print(k, (u, v))

# test

equal_sum_partitions([2, 4, 8, 6, 3, 5])

输出

5 ({5}, {2, 3})
6 ({6}, {2, 4})
7 ({2, 5}, {3, 4})
8 ({8}, {2, 6})
8 ({8}, {3, 5})
8 ({2, 6}, {3, 5})
9 ({4, 5}, {3, 6})
10 ({8, 2}, {4, 6})
10 ({4, 6}, {2, 3, 5})
11 ({8, 3}, {5, 6})
11 ({8, 3}, {2, 4, 5})
13 ({8, 5}, {3, 4, 6})
14 ({8, 6}, {2, 3, 4, 5})
14 ({8, 2, 4}, {3, 5, 6})

这篇关于具有相同总和的子集-python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

Powerset