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.
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
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
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
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))