Find all combinations of list elements including duplicate elements

Question

I am looking for an algorithm in python that will return all possible combinations of a list of numbers that allows for duplicate elements and adds up to a certain number...

For example, given a target number of 7, and a list [2, 3, 4] I would like to be able to generate the combinations below:

2, 2, 3
2, 3, 2
3, 2, 2
3, 4
4, 3

I understand how to get all possible combinations of a list, but I don't know how to include duplicates in this fashion. Any help would be appreciated!

how is 2,2,3 different from 2,3,2? it's not even a permutation — eagle, May 08 '18 at 18:26
it is different in music. I am a musician looking for an algorithm to provide all possible groupings of beats in a bar. — user2145312, May 08 '18 at 18:29

Ajax1234 · Answer 1 · 2018-05-08T18:49:29.823

3

You can create a recursive function and apply the necessary logic:

def combinations(d, current=[], sum_to = 7):
  if sum(current) == 7:
     yield current
  else:
    for i in d:
      if sum(current+[i]) <= 7:
         yield from combinations(d, current+[i])

print(list(combinations([2, 3, 4])))

Output:

[[2, 2, 3], [2, 3, 2], [3, 2, 2], [3, 4], [4, 3]]

edited May 08 '18 at 18:49

answered May 08 '18 at 18:25

Ajax1234

69,937
8
61
102

1

down voted because this is a blatant copy paste from here with just variable names changed ---> https://stackoverflow.com/a/34519260/8746930 – eagle May 08 '18 at 18:31
shouldn't print(list(filter(lambda x:sum(x) == 7, combinations([1,2,3])))) also produce [1,1,1,1,1,1,1]? – Dirk Herrmann May 08 '18 at 18:32
@eagle I did not copy/paste, however, the logic for both answers is very similar. – Ajax1234 May 08 '18 at 18:33
Inspired by @DirkHerrmann's comment: why `len(current) == len(d)` since duplicates are allowed? – jferard May 08 '18 at 18:47

score 1 · Accepted Answer · answered May 08 '18 at 18:40

here is a brute force solution:

def getAllSubsetsWithCertainSum(number_list, target_sum):

    matching_numbers = []

    def recursion(subset):
        for number in number_list:
            if sum(subset+[number]) < target_sum:
                recursion(subset+[number])
            elif sum(subset+[number]) == target_sum:
                matching_numbers.append(subset+[number])

    recursion([])
    return matching_numbers


print(
    getAllSubsetsWithCertainSum([2, 3, 4], 7)
)

If you input a 1 it will also return [1, 1, 1, 1, 1, 1, 1]

this is exactly what i was looking for! simple and works well! — user2145312, May 08 '18 at 19:11

score 0 · Answer 3 · answered May 08 '18 at 21:32

A variation on previous answers, with an important difference: we find only sorted combinations that sums to the target, and then generate the permutations. Example with [2,3,4] and 7:

step 1: find [2,2,3] and [3,4]
step 2: generate permutations: [[2, 2, 3], [2, 3, 2], [3, 2, 2], [3, 4], [4, 3]].

This is really faster. Here's the code (permute_unique was taken from here and optimized with a list comprehension):

def combinations2(d, sum_to):
    def combinations_aux(d, current, sum_to):
        for j in range(len(d)):
          nex = current+[d[j]]
          if sum(nex) == sum_to:
              yield nex
          elif sum(nex) < sum_to:
             yield from combinations_aux(d[j:], nex, sum_to) # d[j:] for elements >= d[j]

    def permute_unique(iterable):
        # see https://stackoverflow.com/a/39014159/6914441
        perms = [[]]
        for i in iterable:
            perms = [perm[:j] + [i] + perm[j:] 
                for perm in perms 
                for j in itertools.takewhile(lambda j:j<1 or perm[j-1] != i, range(len(perm) + 1))
            ]
        return perms

    return (p for c in combinations_aux(sorted(set(d)), [], sum_to) for p in permute_unique(c))

A benchmark (combinations from Ajax1234):

def one(): return list(combinations([2,3,4,5,6,7], 35))
def two(): return list(combinations2([2,3,4,5,6,7], 35))

assert sorted([tuple(t) for t in one()]) == sorted([tuple(t) for t in two()]) 

print (timeit.timeit(one, number=10))
# 154.99560340600146
print (timeit.timeit(two, number=10))
# 23.217042586999014

Find all combinations of list elements including duplicate elements

3 Answers3

Linked