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?

I can't quite get your question. Can you please add the expected aoutput? — alec_djinn, Jul 01 '21 at 11:03
You definitely do not want to generate a list of all permutations that start with 15 _ones_ (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1) and stop with (5,5,5) to sum up to 15 - those are far !!! too many illegal ones that get discarded. The trick is to code smart, not create all and filter - your computers memory can not hold all those permutations. — Patrick Artner, Jul 01 '21 at 11:06

Patrick Artner · Accepted Answer · 2021-07-01T11:49:23.400

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.

Thanks for answering. It is so much helpful, But here, https://math.stackexchange.com/q/2856866 I found that only 13624 solutions for this instead of 2.562.890.625. — VGB, Jul 01 '21 at 13:36

Permutations based on sum without limiting number of items permuted

1 Answers1