How do I generate a list of all possible combinations from a single element in a pair, from numerous pairs nested within a parent list?

user_14497160 0
Viewed 313

I find myself in a unique situation in which I need to multiply single elements within a listed pair of numbers where each pair is nested within a parent list of elements. For example, I have my pre-defined variables as:

output = []
initial_list = [[1,2],[3,4],[5,6]]

I am trying to calculate an output such that each element is the product of a unique combination (always of length len(initial_list)) of a single element from each pair. Using my example of initial_list, I am looking to generate an output of length pow(2 * len(initial_list)) that is scable for any "n" number of pairs in initial_list (with a minimum of 2 pairs). So in this case each element of the output would be as follows:

output[0] = 1 * 3 * 5
output[1] = 1 * 3 * 6
output[2] = 1 * 4 * 5
output[3] = 1 * 4 * 6
output[4] = 2 * 3 * 5
output[5] = 2 * 3 * 6
output[6] = 2 * 4 * 5
output[7] = 2 * 4 * 6

In my specific case, the order of output assignments does not matter other than output[0], which I need to be equivalent to the product of the first element in each pair in initial_list. What is the best way to proceed to generate an output list such that each element is a unique combination of every element in each list?

...

My initial approach consisted of using;

from itertools import combinations 
from itertools import permutations
from itertools import product

to somehow generate a list of every possible combination then multiply the products together and append each product to the output list, but I couldn't figure out a wait to implement the tools successfully. I have since tried to create a recursive function that combines for x in range(2): with nested recursion recalls, but once again I cannot figured out a solution.

Someone more experienced and smarter than me please help me out; Any and all help is appreciated! Thank you!

nested-lists recursion python-3.x list python
5 Answers

Without using any external library

def multi_comb(my_list):
    """
        This returns the multiplication of 
        every possible combinationation of
        the `my_list` of type [[a1, a2], [b1, b2], ...]

        Arg: List
        Return: List
    """
    if not my_list: return [1]

    a, b = my_list.pop(0)
    result = multi_comb(my_list)

    left = [a * i for i in result]
    right = [b * i for i in result]

    return (left + right)
    
print(multi_comb([[1, 2], [3, 4], [5, 6]]))

# Output
# [15, 18, 20, 24, 30, 36, 40, 48]

I am using reccursion to get the result. Here's the visual illustration of how this works.

Instead of taking a top-down approach, we can take bottom-up approach to better understand how this program works.

  1. At the last step, a and b becomes 5 and 6 respectively. Calling multi_comb() with empty list returns [1] as a result. So left and right becomes [5] and [6]. Thus we return [5, 6] to our previous step.

  2. At the second last step, a and b was 3 and 4 respectively. From the last step we got [5, 6] as a result. After multiplying each of the values inside the result with a and b (notice left and right), we return the result [15, 18, 20, 24] to our previous step.

  3. At our first step, that is our starting step, we had a and b as 1 and 2 respectively. The value returned from our last step becomes our result, ie, [15, 18, 20, 24]. Now we multiply both a and b with this result and return our final output.

Note:
This program works only if list is in the form [ [a1, a2], [b1, b2], [c1, c2], ... ] as told by the OP in the comments. The problem of solving the list containing the sub-list of n items will be little different in code, but the concept is same as in this answer.

user_77864460

Look closely, there's an easy pattern. Let there be n sublists, and 2 elements in each: at index 0 and 1. Now, the indexes selected can be represented as a binary string of length n.
It'll start with 0000..000, then 0000...001, 0000...010 and so on. So all you need to do is:

n = len(lst)
for i in range(2**n):
    binary = bin(i)[2:] #get binary representation
    for j in range(n):
        if binary[j]=="1":
            #include jth list's 1st index in product
        else:
            #include jth list's 0th index in product

The problem would a scalable solution would be, since you're generating all possible pairs, the time complexity will be O(2^N)

user_93507200

This problem can also be solved using dynamic programming

output = [1, ]
for arr in initial_list:
    output = [a * b for a in arr for b in product]

This problem is easy to solve if you have just one subarray -- the output is the given subarray.

Suppose you solved the problem for the first n - 1 subarrays, and you got the output. The new subarray is appended. How the output should change? The new output is all pair-wise products of the previous output and the "new" subarray.

user_131186320

Your idea to use itertools.product is great!

import itertools
initial_list = [[1,2],[3,4],[5,6]]
combinations = list(itertools.product(*initial_list))
# [(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]

Now, you can get the product of each tuple in combination using for-loops, or using functools.reduce, or you can use math.prod which was introduced in python 3.8:

import itertools
import math
initial_list = [[1,2],[3,4],[5,6]]
output = [math.prod(c) for c in itertools.product(*initial_list)]
# [15, 18, 20, 24, 30, 36, 40, 48]

import itertools
import functools
import operator
initial_list = [[1,2],[3,4],[5,6]]
output = [functools.reduce(operator.mul, c) for c in itertools.product(*initial_list)]
# [15, 18, 20, 24, 30, 36, 40, 48]

import itertools
output = []
for c in itertools.product(*initial_list):
  p = 1
  for x in c:
    p *= x
  output.append(p)
# output == [15, 18, 20, 24, 30, 36, 40, 48]

Note: if you are more familiar with lambdas, operator.mul is pretty much equivalent to lambda x,y: x*y.

user_30807230

itertools.product and math.prod are a nice fit -

from itertools import product
from math import prod

input = [[1,2],[3,4],[5,6]]
output = [prod(x) for x in product(*input)]
print(output)

[15, 18, 20, 24, 30, 36, 40, 48]
user_6331830
Related