Permutations based on sum without limiting number of items permuted

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)

Here, I want permutations of the elements in the layer_thickness and those sum of the permutations should be to 5. But the number of elements in prmutation is not constrained by any limit unless it gives the desired sum.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 , 2 2 2 2 2 2 2 1, etc are should be an element also.

what modifications should I do to achieve that?

Answer 1

You cant create all permutation as list for any total - it will simply hug too much memory:

• Assuming [1,2,3,4,5] as numbers, 1 is your lowest element.
• Assuming you want to reach a total = 15 - your "biggest" solution is (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1).
• To create all possible permutation of 5 numbers over 15 places you need to create 15**5 list entries: 15**5 = 2.562.890.625 possible number permutations

Storing each combination as 1 byte this would need 2.56 Terabyte of ram. Doubt you got that much.

---

The best you can do is to generate only numbers that work and quit out as soon as you reached your total. To do that for a fixed number set you can start with this question: Finding all possible combinations of numbers to reach a given sum

Using that and provide a "maximized" list of your numbers that can be added up to achieve your goal might lead to something:

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: https://stackoverflow.com/a/4633515/7505395

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))

This will not work for all and any inputs - good luck with your runtime, this will still work reasonably well for a total = 10 - for a total = 15 it will take more time then I needed to format/copy paste and formulate this answer here.