How to generate combinations of elements of different lists?

Question

I have a list of lists that goes like

[[1,2,3],[3,4,5],[5,6,7,8]]

I want to create a program/function that creates a combinations like

1,3,5
1,3,6
1,3,7
1,3,8
1,4,5
1,4,6
.
.
.

If there's a way you can do it without using the itertools module, that would be even more appreciated.

Answer 1

you can use itertools.product

import itertools
a = [[1,2,3],[3,4,5],[5,6,7,8]]
list(itertools.product(*a))
#output
[(1, 3, 5),
 (1, 3, 6),
 (1, 3, 7),
 (1, 3, 8),
 (1, 4, 5),
 (1, 4, 6),
 (1, 4, 7),
 (1, 4, 8),
 (1, 5, 5),
 (1, 5, 6),
 (1, 5, 7),
 (1, 5, 8),
 (2, 3, 5),
 (2, 3, 6),
 (2, 3, 7),
 (2, 3, 8),
 (2, 4, 5),
 (2, 4, 6),
 (2, 4, 7),
 (2, 4, 8),
 (2, 5, 5),
 (2, 5, 6),
 (2, 5, 7),
 (2, 5, 8),
 (3, 3, 5),
 (3, 3, 6),
 (3, 3, 7),
 (3, 3, 8),
 (3, 4, 5),
 (3, 4, 6),
 (3, 4, 7),
 (3, 4, 8),
 (3, 5, 5),
 (3, 5, 6),
 (3, 5, 7),
 (3, 5, 8)]

Answer 2

As you asked for a solution without itertools, this one is a recursive function that takes a list of any length and does the combination you need:

def combine(elems):
    if len(elems) == 0:
        return [[]]
    result = []    
    subcombinations =  combine(elems[1:])
    for x in elems[0]:
        for y in subcombinations:
            result.append([x, *y])
    return result

Or a much shorter version

def combine(elems):
    if len(elems) == 0:
        return [[]]
    return [[x, *y] for x in elems[0] for y in combine(elems[1:])]

Answer 3

This is a roughly equivalent implementation of itertools.product() from documentation in case you want/need to build the function without using a library.

def product(*args, repeat=1):
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

a = [[1,2,3],[3,4,5],[5,6,7,8]]

print(list(product(*a)))

Output:

[(1, 3, 5), (1, 3, 6), (1, 3, 7), (1, 3, 8), (1, 4, 5), (1, 4, 6), (1, 4, 7), (1, 4, 8), (1, 5, 5), (1, 5, 6), (1, 5, 7), (1, 5, 8), (2, 3, 5), (2, 3, 6), (2, 3, 7), (2, 3, 8), (2, 4, 5), (2, 4, 6), (2, 4, 7), (2, 4, 8), (2, 5, 5), (2, 5, 6), (2, 5, 7), (2, 5, 8), (3, 3, 5), (3, 3, 6), (3, 3, 7), (3, 3, 8), (3, 4, 5), (3, 4, 6), (3, 4, 7), (3, 4, 8), (3, 5, 5), (3, 5, 6), (3, 5, 7), (3, 5, 8)]

To print as you wish:

results = list(product(*a))

print('\n'.join([','.join(list(map(str, res))) for res in results]))

Output:

1,3,5
1,3,6
1,3,7
1,3,8
1,4,5
1,4,6
1,4,7
1,4,8
1,5,5
1,5,6
1,5,7
1,5,8
2,3,5
2,3,6
2,3,7
2,3,8
2,4,5
2,4,6
2,4,7
2,4,8
2,5,5
2,5,6
2,5,7
2,5,8
3,3,5
3,3,6
3,3,7
3,3,8
3,4,5
3,4,6
3,4,7
3,4,8
3,5,5
3,5,6
3,5,7
3,5,8

Answer 4

Convert it into linear list and use combinations

from itertools import combinations
linearArr = [ele for ele in row for row in [[1,2,3],[3,4,5],[5,6,7,8]]]
for comb in combinations(linearArr,3):
    print(comb)

Answer 5

Here is how you can use a recursive function:

def comb(arrs, i=0, numbs=[]):
    if i == len(arrs):
        print(*numbs)
        return
    for j in arrs[i]:
        comb(arrs, i + 1, numbs + [j])

arrs = [[1,2,3],[3,4,5],[5,6,7,8]]
comb(arrs)

Output:

1 3 5
1 3 6
1 3 7
1 3 8
1 4 5
1 4 6
1 4 7
1 4 8
1 5 5
1 5 6
1 5 7
1 5 8
2 3 5
2 3 6
2 3 7
2 3 8
2 4 5
2 4 6
2 4 7
2 4 8
2 5 5
2 5 6
2 5 7
2 5 8
3 3 5
3 3 6
3 3 7
3 3 8
3 4 5
3 4 6
3 4 7
3 4 8
3 5 5
3 5 6
3 5 7
3 5 8

Answer 6

I tried two different ways, straight list comprehension and a recursive function.

The list comprehension method is the simplest but assumes your list will only have 3 elements. If you add a fourth set of numbers to your main list, the list comprehension will need to be adjusted to work with it.

In contrast the recursive function is more complicated but will handle an unlimited list of lists with the sub-lists having any number of elements. Of course, it's recursive so a limit will be reached and the time it takes to process the list of lists will be exponentially greater with each additonal list of numbers.

List Comprehension

lol = [
    [1,2,3],
    [3,4,5],
    [5,6,7,8]
]
o = [[x, y, z] for x in lol[0] for y in lol[1] for z in lol[2]]
print(repr(o))

output

[
  [1, 3, 5],
  [1, 3, 6],
  [1, 3, 7],
  [1, 3, 8],
  [1, 4, 5],
  ...
  [3, 5, 6],
  [3, 5, 7],
  [3, 5, 8]
]

Recursive function

def stich(l: list) -> list:
    def merge(a, b):
        if not a:
            return [[y,] for y in b]
        return [x + [y,] for x in a for y in b]
    ol = []
    tl = l.copy()
    while tl:
        ol = merge(ol, tl.pop(0))
    return ol


stiched_list = stich(lol)
print(repr(stiched_list))

output

[
  [1, 3, 5],
  [1, 3, 6],
  [1, 3, 7],
  [1, 3, 8],
  [1, 4, 5],
  ...
  [3, 5, 6],
  [3, 5, 7],
  [3, 5, 8]
]