2

I'd like to modify the subset_sum() python function from Finding all possible combinations of numbers to reach a given sum so that:

  1. It allows repeats (permutations) instead of combinations
  2. It only considers permutations of a given length

I've successfully accomplished #2, but I need assistance with #1:

def subset_sum(numbers, target, length, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target and len(partial) == length:
        print(f"sum({partial})={target}")
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, length, partial + [n])

The desired output should be:

>>> subset_sum([3,9,8,4,5,7,10],target=15,length=3)
sum([3, 8, 4])=15
sum([3, 4, 8])=15
sum([4, 3, 8])=15
sum([4, 8, 3])=15
sum([8, 3, 4])=15
sum([8, 4, 3])=15
sum([3, 5, 7])=15
sum([3, 7, 5])=15
sum([5, 3, 7])=15
sum([5, 7, 3])=15
sum([7, 3, 5])=15
sum([7, 5, 3])=15
justin
  • 171
  • 8

2 Answers2

2

Since you've solved the problem of identifying one solution in each equivalence group, my advice is: do not alter that algorithm. Instead, harness itertools.permutations to generate those items:

return list(itertools.permutations(numbers))
Prune
  • 76,765
  • 14
  • 60
  • 81
  • Yes, this is a good idea. Can you elaborate on how to return the list of numbers from this recursive function rather than just printing them to the screen? – justin Oct 26 '18 at 00:04
  • The `list` expression above gets inserted before the final return from the function. You can check `partial` to see whether this is the top-level invocation. – Prune Oct 26 '18 at 00:29
2

This does it:

import itertools

numbers = [3,9,8,4,5,7,10]
length = 3
target = 15

iterable = itertools.permutations(numbers,length)
predicate = lambda x: (sum(x) == target)
vals = filter(predicate,iterable)
list(vals)

Or a one-liner:

vals = [x for x in itertools.permutations(numbers,length) if sum(x) == target]

Results:

[(3, 8, 4),
 (3, 4, 8),
 (3, 5, 7),
 (3, 7, 5),
 (8, 3, 4),
 (8, 4, 3),
 (4, 3, 8),
 (4, 8, 3),
 (5, 3, 7),
 (5, 7, 3),
 (7, 3, 5),
 (7, 5, 3)]
justin
  • 171
  • 8