python-3.x 整数表划分为K个和相等的子表

pu82cl6c 于 2023-02-06 发布在 Python

关注(0)|答案(1)|浏览(101)

类似的问题还有1和2，但答案没有帮助。假设我们有一个整数列表，我们想找到K个不相交列表，使它们完全覆盖给定列表，并且具有相同的和。例如，如果A = [4, 3, 5, 6, 4, 3, 1]和K = 2，则答案应为：

[[3, 4, 6], [1, 3, 4, 5]]
or
[[4, 4, 5], [1, 3, 3, 6]]

我写了一个代码，只有当K = 2和它的工作很好的小列表作为输入，但与非常大的列表，因为代码的高复杂性，操作系统终止任务.我的代码是：

def subarrays_equal_sum(l):
    from itertools import combinations

    if len(l) < 2 or sum(l) % 2 != 0:
        return []
    l = sorted(l)
    list_sum = sum(l)
    all_combinations = []
    for i in range(1, len(l)):
        all_combinations += (list(combinations(l, i)))

    combinations_list = [i for i in all_combinations if sum(i) == list_sum / 2]
    if not combinations_list:
        return []
    final_result = []
    for i in range(len(combinations_list)):
        for j in range(i + 1, len(combinations_list)):
            first = combinations_list[i]
            second = combinations_list[j]
            concat = sorted(first + second)
            if concat == l and [list(first), list(second)] not in final_result:
                final_result.append([list(first), list(second)])

    return final_result

K的任何值的答案都是here。但是如果我们传递参数A = [4, 3, 5, 6, 4, 3, 1]和K = 2，它们的代码只返回[[5, 4, 3, 1],[4, 3, 6]]，而我的代码返回所有可能的列表，即：
[[[3, 4, 6], [1, 3, 4, 5]], [[4, 4, 5], [1, 3, 3, 6]]]
我的问题是：
1.如何降低代码的复杂性和成本？
1.如何让我的代码可以处理k的任意值？

python-3.x

来源：https://stackoverflow.com/questions/75342160/partition-of-a-list-of-integers-into-k-sublists-with-equal-sum

1条答案

按热度按时间

6rqinv9w1#

这有大量潜在的解决方案，因此，减少要评估的合格模式的数量将是提高性能的关键。
我有个想法：分两步走：
1.生成加起来等于所述目标相等和的索引组的列表。
1.合并不相交的索引组（这样索引就只在一个组中），这样就得到K个组。
assemble函数是一个递归生成器，它将生成不重叠的n索引组合（集合）的列表。假定每个组都有一个总计/K的和，则列表将完全覆盖原始列表元素。

def assemble(combos,n):
    if not n:
        yield []
        return
    if len(combos)<n: return
    for i,idx in enumerate(combos):
        others = [c for c in combos if c.isdisjoint(idx)]
        for rest in assemble(others,n-1):
            yield [idx] + rest
            
def equalSplit(A,K):
    total = sum(A) 
    if total%K: return       # no equal sum solution
    partSum = total//K       # sum of each resulting sub-lists
    combos = [ (0,[]) ]      # groups of indices that form sums <= partSum
    for i,n in enumerate(A): # build the list of sum,patterns 
        combos += [ (tot+n,idx+[i]) for tot,idx in combos
                    if tot+n <= partSum]
    # only keep index sets that add up to the target sum
    combos = [set(idx) for tot,idx in combos if tot == partSum]
    # ouput assembled lists of K sets that don't overlap (full coverage)
    seen = set()
    for parts in assemble(combos,K):
        sol = tuple(sorted(tuple(sorted(A[i] for i in idx)) for idx in parts))
        if sol in seen: continue # skip duplicate solutions
        yield list(sol)
        seen.add(sol)

输出：

A = [4, 3, 5, 6, 4, 3, 1]
print(*equalSplit(A,2), sep='\n')
# [(1, 3, 4, 5), (3, 4, 6)]
# [(1, 3, 3, 6), (4, 4, 5)]

A = [21,22,27,14,15,16,17,18,19,10,11,12,13]
print(*equalSplit(A,5), sep='\n')
# [(10, 15, 18), (11, 13, 19), (12, 14, 17), (16, 27), (21, 22)]
# [(10, 14, 19), (11, 15, 17), (12, 13, 18), (16, 27), (21, 22)]

对于分成几个部分的大型列表，这仍然需要很长时间，但它应该比组合的暴力更好一点 *

赞(0）回复(0）举报 2023-02-06

我来回答

python-3.x 整数表划分为K个和相等的子表

1条答案

相关问题

热门标签

最新问答