In Python I have a list of n lists, each with a variable number of elements. How can I create a single list containing all the possible permutations:
For example
[ [ a, b, c], [d], [e, f] ]
I want
[ [a, d, e] , [a, d, f], [b, d, e], [b, d, f], [c, d, e], [c, d, f] ]
Note I don't know n in advance. I thought itertools.product would be the right approach but it requires me to know the number of arguments in advance
You don't need to know n in advance to use itertools.product
>>> import itertools
>>> s=[ [ 'a', 'b', 'c'], ['d'], ['e', 'f'] ]
>>> list(itertools.product(*s))
[('a', 'd', 'e'), ('a', 'd', 'f'), ('b', 'd', 'e'), ('b', 'd', 'f'), ('c', 'd', 'e'), ('c', 'd', 'f')]
You can do it with a multi-level list comprehension:
>>> L1=['a','b','c']
>>> L2=['d']
>>> L3=['e','f']
>>> [[i,j,k] for i in L1 for j in L2 for k in L3]
[['a', 'd', 'e'], ['a', 'd', 'f'], ['b', 'd', 'e'], ['b', 'd', 'f'], ['c', 'd', 'e'], ['c', 'd', 'f']]
n (n = 3 in your answer) :)
itertools.product works for me.
>>> l=[ [ 1, 2, 3], [4], [5, 6] ]
>>> list(itertools.product(*l))
[(1, 4, 5), (1, 4, 6), (2, 4, 5), (2, 4, 6), (3, 4, 5), (3, 4, 6)]
>>> l=[ [ 1, 2, 3], [4], [5, 6],[7,8] ]
>>> list(itertools.product(*l))
[(1, 4, 5, 7), (1, 4, 5, 8), (1, 4, 6, 7), (1, 4, 6, 8), (2, 4, 5, 7), (2, 4, 5, 8), (2, 4, 6, 7), (2, 4, 6, 8), (3, 4, 5, 7), (3, 4, 5, 8), (3, 4, 6,
7), (3, 4, 6, 8)]
>>>
If, for some reason, you need to define your own method and not use itertools.product (e.g., for a interview question):
from typing import Any, Optional
def cartesian_product(values: list[list[Any]],
partial_result: Optional[list[Any]] = None,
result: Optional[list[list[Any]]] = None) -> list[list[Any]]:
"""
Computes the cartesian product of a list of lists. This function is a
recursive implementation and gives the same output as the function
itertools.product() from the Python standard library.
:param values: A list of lists for which the cartesian product is computed.
:param partial_result: A list that accumulates the current combination of values.
This parameter is mainly used during the recursion.
:param result: A list of all combinations that have been considered so far.
This parameter is mainly used during the recursion.
:return: A list of lists, where each inner list is one combination of
elements from the input lists.
"""
if partial_result is None:
partial_result = []
if result is None:
result = []
if values:
for v in values[0]:
cartesian_product(values[1:], partial_result + [v], result)
else:
result.append(partial_result)
return result
print(f"{cartesian_product([['a', 'b', 'c'], ['d'], ['e', 'f']]) = }")
print(f"{cartesian_product([[1, 2, 3], [4], [5, 6]]) = }")
Output:
cartesian_product([['a', 'b', 'c'], ['d'], ['e', 'f']]) = [['a', 'd', 'e'], ['a', 'd', 'f'], ['b', 'd', 'e'], ['b', 'd', 'f'], ['c', 'd', 'e'], ['c', 'd', 'f']]
cartesian_product([[1, 2, 3], [4], [5, 6]]) = [[1, 4, 5], [1, 4, 6], [2, 4, 5], [2, 4, 6], [3, 4, 5], [3, 4, 6]]
