CODEWITHSUNDEEP
python
Tony Lucas
Tony Lucas

Reputation: 195

How to generate all the combinations of the elements from an array in order?

I want to get all the combinations of an array's element in the following order. say: a = [2, 3, 5], then after I call mysterious(a), I should get another array that is: [2, 3, 5, 2 * 3, 2 * 5, 3 * 5, 2 * 3 * 5] or [2, 3, 5, 6, 10, 15, 30]. Note: must be directly in this order.

To make my question more clear:

  1. when lst = [2, 3, 5, 7], the return lst should be [2, 3, 5, 7, 2 * 3, 2 * 5, 2 * 7, 3 * 5, 3 * 7, 5 * 7, 2 * 3 * 5, 2 * 3 * 7, 2 * 5 * 7, 3 * 5 * 7, 2 * 3 * 5 * 7] or [2, 3, 5, 7, 6, 10, 14, 15, 21, 35, 30, 42, 70, 105, 210]

  2. you can think of the returnList is in the order of (nCr n chooses r) nC1, nC2, ..., nCn.

  3. I am asking for a generic answer, you should handle arbitrary length of input list.

I can apply a recursion algorithm to derive all the combinations, but due to how recursion works, I can only get [2, 3, 2 * 3, 5, 2 * 5, 3 * 5, 2 * 3 * 5] or [2, 3, 6, 5, 10, 15, 30], which is in a wrong order. See my code below:

def listBuilding(lst):
    length = len(lst)
    if len(lst) == 2:
        return [lst[0], lst[1], lst[0] * lst[1]]
    else:
        previous = listBuilding(lst[:(length - 1)])
        return previous + [lst[length - 1]] + [(lst[length - 1] * x) for x in previous]

Can someone help me? I think this should be a common problem, and someone might have answered this before, but I cannot find it. I am expecting an easy answer.

Upvotes: 2

Views: 1564

Answers (1)

U13-Forward
U13-Forward

Reputation: 71580

You might need to use functools.reduce and itertools.combinations and operator.mul with a nested for loop which does it, also add a and l at the end:

>>> from functools import reduce
>>> from itertools import combinations
>>> import operator
>>> a = [2, 3, 5]
>>> l = []
>>> for i in range(2, len(a) + 1):
    for x in combinations(a, i):
        l.append(reduce(operator.mul, x, 1))


>>> a + l
[2, 3, 5, 6, 10, 15, 30]
>>>

Upvotes: 2

Related Questions