Efficient way to find partial permutations of list equal to a specific sum

Question

I have a set of float values and I need all the possible permutations that, added together, result in a specific number. Furthermore, I need all permutations to contain exactly eight values.

So, for example, I have the following set of values:

[0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]

I need to get all the permutations of 8 elements that add up to 20.

A code that works is the following:

N = [0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]
target = 20

accum = 0

for i1 in N:
  accum += i1
  for i2 in N:
    accum += i2
    for i3 in N:
      accum += i3
      for i4 in N:
        accum += i4
        for i5 in N:
          accum += i5
          for i6 in N:
            accum += i6
            for i7 in N:
              accum += i7
              for i8 in N:
                accum += i8
                if accum > target:
                  accum -= i8
                  break
                elif accum == target:
                  print(i1, i2, i3, i4, i5, i6, i7, i8)
                  accum -= i8
                  break
                accum -= i8
              accum -= i7
            accum -= i6
          accum -= i5
        accum -= i4
      accum -= i3
    accum -= i2
  accum -= i1

And some of the results are given like this:

0.5 0.5 0.5 0.5 0.5 0.5 2 15
0.5 0.5 0.5 0.5 0.5 0.5 15 2
0.5 0.5 0.5 0.5 0.5 1.5 1 15
0.5 0.5 0.5 0.5 0.5 1.5 15 1
0.5 0.5 0.5 0.5 0.5 2 0.5 15
0.5 0.5 0.5 0.5 0.5 2 3 12.5
0.5 0.5 0.5 0.5 0.5 2 12.5 3
0.5 0.5 0.5 0.5 0.5 2 15 0.5
0.5 0.5 0.5 0.5 0.5 2.5 2.5 12.5
0.5 0.5 0.5 0.5 0.5 2.5 5 10
0.5 0.5 0.5 0.5 0.5 2.5 7.5 7.5
0.5 0.5 0.5 0.5 0.5 2.5 10 5
0.5 0.5 0.5 0.5 0.5 2.5 12.5 2.5
0.5 0.5 0.5 0.5 0.5 3 2 12.5

I can filter the results later with excel. I don't need the code to be sophisticated, I just need the final set of results. As one can see, this code is extremely inefficient, as it takes a lot of time to process, and also gives a great amount of duplicate values. I don't have deep programming knowledge but I know recursive methods are far more efficient. How can I get the results I need?

Answer 1

The easiest way is using itertools and list comprehension:

import itertools

# Inputs
N = [0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]
target = 20

# Operation
list_sum=[item for item in itertools.product(N, repeat=8) if sum(item)==target]

# Printing
print(list_sum)

To see the kind of output you get, if you use 2 elements only, the following output is obtained:

[(2.5, 17.5), (5, 15), (7.5, 12.5), (10, 10), (12.5, 7.5), (15, 5), (17.5, 2.5)]

This is not the fastest solution (a recursive function is more optimal). Note that I provide all the possible permutations since I have assumed that the order of the elements may be important. Otherwise, the execution time can be reduced.

Answer 2

Here is a recursive solution. The efficiency gains depend on:

• Inside the recursive call, do not iterate over the whole list, just the remaining portion of the list.

• No need to fully sum every combination from scratch in order to test it, just subtract off the value from target as you iterate.

A further efficiency gain is possible in this case, relying on the fact that the list only contains positive numbers, so if a particular value would overshot the target then you do not need to make the recursive call (the elif val < target test). Without this fact, that part of the code would need to be unconditional, and then it would take longer.

The test case took 0.04 seconds on an oldish machine.

def yield_combos(N, num, target):
    for i, val in enumerate(N):
        if num == 1:
            if val == target:
                yield [val]
        elif val < target:
            for j in yield_combos(N[i:], num - 1, target - val):
                yield [val] + j
    

N = [0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]
target = 20
num = 8
                    
for combo in yield_combos(N, num, target):
    print(f"combo={combo} length={len(combo)} total={sum(combo)}")

This gives:

combo=[0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 2, 15] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 1, 1.5, 15] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2, 3, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2.5, 2.5, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2.5, 5, 10] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2.5, 7.5, 7.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 5, 5, 7.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 1, 1, 15] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 1.5, 3, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 2, 2.5, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 2, 5, 10] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 2, 7.5, 7.5] length=8 total=20.0
... etc ...

The above is on the basis that it is permissible to repeat elements. If not, then use N[i+1:] instead of N[i:] in the recursive call, although in that case there are no solutions for target 20.

Note also that this gives each solution only in order of increasing index in the input list (in this case increasing value because the input list happens to be sorted), rather than every permutation of them, based on the understanding that extra permutations are "duplicate values" that the question implies should be avoided. However, if additionally permutations are required, then the efficient thing to do would be do the search initially exactly as above (not loop over the entire list in the recursive call), but then permute only the elements of the solutions as a final step.

Answer 3

import itertools

def func(list, size_perm, target):
     #Generate all permutations
     perms = itertools.permutations(list, size_perm)
     
     #iterate of all permutations and print only if sum == target
     for item in perms:
         if sum(item) == target:
             print(item)
N = [0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]
func(N, 8, 20)

Not too sure if this is the most efficient method, but this should work. Let me know if it doesn't work.