Finding all possible combination on python

Question

I am trying to find all combination of numbers in a list that gives a certain number on python 2.7.Tried combinations of itertool but can't quite figure it out,so here it goes.

mylist=[1,2,3,4,5,6,7,8,9,10]
number=60 # for 3 elements

results=[[3,4,5],[2,3,10],[2,5,6],[1,6,10]...]

I tried

import itertools

num = [1, 2, 3, 4, 5,6,7,8,9,10]
combinations = []

for combination in itertools.combinations(num, 3):
    combinations.append(int("".join(str(i) for i in combination)))
    print combinations

# ...
combination=[123,124,125....]

You want all combinations that gives 60 when multiplied, right ? — Scharron
– Scharron, Commented Dec 21, 2012 at 10:23

Scharron · Accepted Answer · 2012-12-21 10:27:47Z

3

import itertools

num = [1, 2, 3, 4, 5,6,7,8,9,10]
combinations = itertools.combinations(num, 3)
matching = [c for c in combinations if reduce(lambda x, y: x * y, c, 1) == 60]

print(matching)

The magic line is the matching = [c for c in combinations if reduce(lambda x, y: x * y, c, 1) == 60]. It's a list comprehension, equivalent to :

matching = []
for c in combinations:
  if reduce(lambda x, y: x * y, c, 1) == 60:
    matching.append(c)

You can find documentation about the reduce function here

answered Dec 21, 2012 at 10:27

Scharron

17.9k6 gold badges46 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Jim DeLaHunt Over a year ago

@user1921180, if you like this answer, please reward Scharron by marking it "correct".

Ashwini Chaudhary Over a year ago

reduce(operator.mul,c) is better than reduce(lambda x, y: x * y, c, 1).

Goranek Over a year ago

@Ashwini yeah but reduce isn't available in python3 ..well there is in functools.reduce but still

Sufian Latif · Accepted Answer · 2012-12-21 12:17:20Z

Though it has been answered, here's a recursive algorithm to find combinations:

def findCombination(product, numList, length, minimum):
    if length == 0 and product == 1:
        return [[]]
    if length == 1 and product in numList and product > minimum:
        return [[product]]

    ret = []
    subList = [item for item in numList if item > minimum]
    for n in subList:
        if product % n == 0:
            temp = findCombination(product / n, subList, length - 1, n)
            for x in temp:
                ret += [[n] + x]
    return ret

To make it work correctly, mylist has to be sorted, because the combinations are made in ascending order.

>>> mylist=[1,2,3,4,5,6,7,8,9,10]
>>> mylist = sorted(mylist)
>>> number = 60
>>> print findCombination(number, mylist, 3, mylist[0])
[[1, 6, 10], [2, 3, 10], [2, 5, 6], [3, 4, 5]]

Goranek · Accepted Answer · 2012-12-21 10:46:28Z

>>> import itertools
>>> numbers = 1,2,3,4,5,6,7,8,9

>>> combinations =  itertools.combinations(numbers,3)

>>> ["".join([str(a),str(b), str(c)]) for a, b, c in combinations if a*b*c == 60]
['256', '345']

This will work with N combinations needed

>>> import itertools, operator
>>> numbers = 1,2,3,4,5,6,7,8,9,10
>>> multiply_must_be = 60

>>> combinations = itertools.combinations(numbers, 3)

>>> combine = lambda arr: "".join([str(item) for item in arr])
>>> multiply = lambda arr: reduce(operator.mul, arr, 1)

>>> [combine(combo) for combo in combinations if multiply(combo) == multiply_must_be]
['1610', '2310', '256', '345']

Collectives™ on Stack Overflow

Finding all possible combination on python

3 Answers 3

3 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Related