Help with list all possible combination

python

#1

I want to create a program wich gives me all possible combination to make a certain number.

So, lets say i want all possible ways to make 15 with 3 digits with the numbers 1 till 9 (9 included), this is simple:

# python2
result = []
for a in range(1,10):
  for b in range(1,10):
    for c in range(1,10):
      x = [a,b,c]
      x.sort()
      if a + b + c == 15:
        if len(set(x)) == 3:
          if x not in result:
            result.append(x)
print result

with 4 or 5 digits, its also easy, you just add one or two more loops. The part where i get stuck is if i let the user choice how many digits he wants (3, 4 or 5 digits), because then, i can't hard code the loop.

Can somebody help me in the right direction?


#2

Perhaps a while loop?

# python 3
number = int(input("number: "))
i = 1

while i <= number:
  print(i)
  i += 1

#3

a while loop sounds perfectly logic, i attempted that, but didn't posted it here given i didn't get anywhere close


#4

i mean, yes, this works:

size = int(raw_input("size: "))
result = []
if size == 3:
  for a in range(1,10):
    for b in range(1,10):
      for c in range(1,10):
        x = [a,b,c]
        x.sort()
        if a + b + c == 21:
          if len(set(x)) == 3:
            if x not in result:
              result.append(x)
elif size == 4:
  for a in range(1,10):
    for b in range(1,10):
      for c in range(1,10):
        for d in range(1, 10):
          x = [a,b,c,d]
          x.sort()
          if a + b + c + d == 21:
            if len(set(x)) == 4:
              if x not in result:
                result.append(x)
elif size == 5:
  for a in range(1,10):
    for b in range(1,10):
      for c in range(1,10):
        for d in range(1, 10):
          for e in range(1, 10):
            x = [a,b,c,d,e]
            x.sort()
            if a + b + c + d + e == 21:
              if len(set(x)) == 5:
                if x not in result:
                  result.append(x)
  
print result

but it kind of sucks, and isn't really DRY


#5

This is a great way to use recursion!

First, declare a list that will hold all your combinations combinations = []
Then make a recursive function:

combinations = []
def makeNumber(number, digits, path = []):
      if baseCase:
              # add to combinations
      else:
           for range:
                 recurse

Full Code:

def makeNumber(number, digits, path = []):
    if digits == 1:
        path += [number]
        path.sort()
        if number < 10 and path not in combinations:
            combinations.append(path)
        return
    else:
        for i in range(1, min(number - digits + 2, 10)):
            makeNumber(number - i, digits - 1, path + [i])

combinations = []
makeNumber(9,2)
print(len(combinations))

You'd need to add extra cases to handle numbers that are too big to be made, or negative numbers, but this is a good start :slight_smile:


#6

recursion indeed sounds good, why didn't i think of that? if you have unknown numbers, recursion is good


#7

Just updated it with a template ^^ full code is in the spoiler :smiley:


#8

if i need to calculate 30 with 5 digits, it throws a recursion depth reached

not that i am ungrateful, but it seems i need to apply some optimazation


#9

Just updated the code, some slowness is due to python printing out a lot of numbers, try just printing the length instead.


#10

One pretty funky way of doing it is in a oneliner:

import itertools as it
def makeNumber(number, digits):
    return list(filter(lambda x: sum(x) == number, it.combinations_with_replacement(range(1,10), digits)))

combinations = makeNumber(30,5)
print(combinations)
  • Itertools creates all possible combinations of the many digits.
  • lambda assigns Truth statements to whether the sum equals the number for each possible combination.
  • filter gets rid of any combinations that don't equal the sum.
  • list turns the filter object into a nicer form.

#11

i wanted unique digits only, i thought of this:

import itertools as it
def makeNumber(number, digits):
    return list(filter(lambda x: sum(x) == number and len(set(x)) == digits, it.combinations_with_replacement(range(1,10), digits)))

combinations = makeNumber(11,4)
print(combinations)

any good?


#12

Yeah, that would work, but your checking a lot more combinations than you need to, and there's an overhead to the len(set(x)) part, there's a nice function called it.combinations which makes sure the numbers are unique.

I've also shown a way to do it without using itertools :slight_smile:

def makeNumber(number, digits, path = []):
    if digits == 1:                   # base case when only 1 digit to play with
        if number not in path:        # to stop duplications
            path += [number]          # digit must be remaining number 
            path.sort()               # sort to stop duplicates
            if number < 10 and path not in combinations:   # make sure number is only 1-9
                combinations.append(path)    # add to combinations

    else:
        nums = list(range(1, min(number - digits + 2, 10)))   # all possible digits 
        nums = list(set(nums).difference(path))               # get rid of those already in path 

        for i in nums:
            makeNumber(number - i, digits - 1, path + [i])    # recurse


import itertools as it
def makeNumber2(number, digits):
    return list(filter(lambda x: sum(x) == number, it.combinations(range(1,10), digits)))

combinations = []
makeNumber(15,3)
print(combinations)
print(makeNumber2(15,3))