How to get the Cartesian product of multiple lists

Как я могу получить декартово произведение (все возможные комбинации значений) из группы списков?

Например, учитывая

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

Как мне это получить?

[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), (2, 'a', 5), ...]

_{Одно из распространенных применений этого метода - избегать глубоко вложенных циклов. Более конкретный дубликат см. в разделе Избегание вложенных циклов for. Аналогично, этот метод может быть использован для "разбиения" словаря на значения списка; см. Объединение перестановок словаря Python в список словарей .}

_{Если вы хотите получить декартово произведение одного и того же списка с самим собой несколько раз, itertools.product можете справиться с этим элегантно. Смотрите Операции над каждой парой элементов в списке или Как я могу получить "перестановки с повторениями" из списка (декартово произведение списка на самого себя)?.}

_{Многие люди, которые уже знают о itertools.product, сталкиваются с тем фактом, что он ожидает отдельные аргументы для каждой входной последовательности, а не, например, список списков. Принятый ответ показывает, как справиться с этим с помощью *. Однако использование * здесь для распаковки аргументов принципиально не отличается от любого другого использования в вызове функции. Пожалуйста, ознакомьтесь с Расширением кортежей в аргументы в этом разделе (и используйте это вместо этого, чтобы закрывать повторяющиеся вопросы, при необходимости).}

Используйте itertools.product, который доступен с Python 2.6.

import itertools

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]
for element in itertools.product(*somelists):
    print(element)

Это то же самое, что:

for element in itertools.product([1, 2, 3], ['a', 'b'], [4, 5]):
    print(element)

import itertools
>>> for i in itertools.product([1,2,3],['a','b'],[4,5]):
...         print i
...
(1, 'a', 4)
(1, 'a', 5)
(1, 'b', 4)
(1, 'b', 5)
(2, 'a', 4)
(2, 'a', 5)
(2, 'b', 4)
(2, 'b', 5)
(3, 'a', 4)
(3, 'a', 5)
(3, 'b', 4)
(3, 'b', 5)
>>>

Для Python 2.5 и старше:

>>> [(a, b, c) for a in [1,2,3] for b in ['a','b'] for c in [4,5]]
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]

Вот рекурсивная версия product() (просто иллюстрация):

def product(*args):
    if not args:
        return iter(((),)) # yield tuple()
    return (items + (item,) 
            for items in product(*args[:-1]) for item in args[-1])

Пример:

>>> list(product([1,2,3], ['a','b'], [4,5])) 
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]
>>> list(product([1,2,3]))
[(1,), (2,), (3,)]
>>> list(product([]))
[]
>>> list(product())
[()]

Я бы использовал понимание списка:

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

cart_prod = [(a,b,c) for a in somelists[0] for b in somelists[1] for c in somelists[2]]