基于总和的排列而不限制排列的项目数

Question

import itertools as itt

layer_thickness=[1,2,3,4,5]
permu= itt.permutations(layer_thickness,5)
permu_list=list(permu)
for i in permu_list:
    if sum(i)==15:
        print(i)

在这里，我想要 layer_thickness 中元素的排列，这些排列的总和应该是 5。但是 prmutation 中的元素数量不受任何限制，除非它给出所需的总和。

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 , 2 2 2 2 2 2 2 1, etc 也应该是一个元素。

我应该做哪些修改才能实现？

Answer 1

您不能将所有排列创建为任何总数的列表 - 它只会占用太多内存：

假设 [1,2,3,4,5] 作为数字，1 是你的最低元素。
假设您想达到 total = 15 - 您的“最大”解决方案是 (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1).
要在 15 个位置创建 5 个数字的所有可能排列，您需要创建 15**5 列表条目：15**5 = 2.562.890.625 个可能的数字排列

将每个组合存储为 1 个字节，这需要 2.56 Terabyte 内存。怀疑你有那么多。

您最好只生成有效的数字，并在达到总数后立即退出。要为固定数字集执行此操作，您可以从这个问题开始：Finding all possible combinations of numbers to reach a given sum

使用它并提供一个“最大化”的数字列表，可以将这些数字相加以实现您的目标可能会导致一些结果：

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Credit:

def calc_nums_for_permutate(nums, total):
    """Creates a list of numbers from num - each single number is added as
    many times as itself fits into total"""
    return [n for n in nums for _ in range(total//n)]

if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]
    total = 15
    
    print( *subset_sum( calc_nums_for_permutate(nums, total), total))

这不适用于所有和任何输入 - 祝你运行时好运，这对于 total = 10 仍然相当有效 - 对于 total = 15 它将花费比我需要更多的时间format/copy 在此处粘贴并制定此答案。

基于总和的排列而不限制排列的项目数

Permutations based on sum without limiting number of items permuted

python

combinations

permutation

itertools