Получить декартово произведение из серии списков?

317

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

Входные данные:

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) ...]
ʞɔıu
источник
24
Имейте в виду, что «каждая возможная комбинация» не совсем совпадает с «декартовым произведением», поскольку в декартовых произведениях допускаются дубликаты.
Триптих
7
Есть ли неповторяющаяся версия декартового произведения?
KJW
16
@KJW Да,set(cartesian product)
NoBugs
5
В декартовом произведении не должно быть дубликатов, если только входные списки не содержат сами дубликаты. Если вы не хотите дубликатов в декартовом произведении, используйте set(inputlist)над всеми вашими входными списками. Не на результат.
CamilB
@ Триптих что? Стандартное определение декартового произведения - это набор. Почему так много людей поддерживают?
PascalIv

Ответы:

378

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)
Триптих
источник
22
Просто хотел добавить символ '*' требуется, если вы используете переменные somelists, как предусмотрено OP.
Брайан Бак
1
@jaska: product()генерирует nitems_in_a_list ** nlistsэлементы в результате ( reduce(mul, map(len, somelists))). Нет оснований полагать, что получение одного элемента не является O(nlists)(амортизированным), т. Е. Сложность по времени такая же, как и для простых вложенных forциклов, например, для ввода в вопросе:, nlists=3общее количество элементов в результате: 3*2*2и каждый элемент имеет nlistsэлементы ( 3в данном случае).
Jfs
2
Какая польза от некоторых *списков? Что оно делает?
Винеет Кумар Доши
6
@VineetKumarDoshi: здесь он используется для распаковки списка в несколько аргументов вызова функции. Подробнее здесь: stackoverflow.com/questions/36901/…
Моберг
4
Примечание: Это работает только если каждый список содержит , по меньшей мере , один элемент
Igo
84
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)
>>>
Джейсон Бейкер
источник
38

Для 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())
[()]
JFS
источник
Рекурсивная версия не работает, если некоторые из них argsявляются итераторами.
JFS
20

с itertools.product :

import itertools
result = list(itertools.product(*somelists))
SilentGhost
источник
6
Какая польза от некоторых *списков?
Винеет Кумар Доши
@VineetKumarDoshi "product (somelists)" - декартово произведение между подсписками, в котором Python сначала получает "[1, 2, 3]" в качестве элемента, а затем получает другой элемент после следующего запятой, и это перевод строки, поэтому первый продукт термин ([1, 2, 3],), аналогично второму ([4, 5],) и т. д. [([1, 2, 3],), ([4, 5],), ( [6, 7],)] " . Если вы хотите получить декартово произведение между элементами внутри кортежей, вам нужно сообщить Python с Asterisk о структуре кортежей. Для словаря вы используете **. Больше здесь .
HHH
19

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

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]]
user1035648
источник
1
Мне действительно нравится это решение с использованием списочных представлений. Я не знаю, почему не проголосовали больше, это так просто.
llekn
20
@llekn, потому что код, кажется, фиксируется на количество списков
Bằng
11

Вот рекурсивный генератор, который не хранит никаких временных списков

def product(ar_list):
    if not ar_list:
        yield ()
    else:
        for a in ar_list[0]:
            for prod in product(ar_list[1:]):
                yield (a,)+prod

print list(product([[1,2],[3,4],[5,6]]))

Вывод:

[(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]
Анураг Униял
источник
1
Они хранятся в стеке, хотя.
Квентин Праде
@QuentinPradet, ты имеешь в виду, что генератор like def f(): while True: yield 1будет продолжать увеличивать размер своего стека по мере его прохождения?
Анураг Униял
@QuentinPradet да, но даже в этом случае для максимальной глубины нужен только стек, а не весь список, поэтому в этом случае стек 3
Anurag Uniyal
Это правда, извините. Тест может быть интересным. :)
Квентин Прадет,
11

В Python 2.6 и выше вы можете использовать itertools.product. В старых версиях Python вы можете использовать следующий (почти - см. Документацию) эквивалентный код из документации , по крайней мере, в качестве отправной точки:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Результатом обоих является итератор, поэтому, если вам действительно нужен список для дальнейшей обработки, используйте list(result).


источник
Согласно документации, фактическая реализация itertools.product НЕ дает промежуточных результатов, которые могут быть дорогими. Использование этой техники может довольно быстро выйти из-под контроля для списков среднего размера.
Триптих
4
я могу только указать ОП на документацию, но не читать ее для него.
1
Код из документации предназначен для демонстрации того, что делает функция продукта, а не как обходной путь для более ранних версий Python.
Триптих
9

Хотя ответов уже много, я хотел бы поделиться некоторыми своими мыслями:

Итеративный подход

def cartesian_iterative(pools):
  result = [[]]
  for pool in pools:
    result = [x+[y] for x in result for y in pool]
  return result

Рекурсивный подход

def cartesian_recursive(pools):
  if len(pools) > 2:
    pools[0] = product(pools[0], pools[1])
    del pools[1]
    return cartesian_recursive(pools)
  else:
    pools[0] = product(pools[0], pools[1])
    del pools[1]
    return pools
def product(x, y):
  return [xx + [yy] if isinstance(xx, list) else [xx] + [yy] for xx in x for yy in y]

Лямбда-подход

def cartesian_reduct(pools):
  return reduce(lambda x,y: product(x,y) , pools)
weiyixie
источник
В «Итеративном подходе», почему результат объявляется как результат = [[]], я знаю, что это list_of_list, но в целом, даже если мы объявили list_of_list, мы используем [], а не [[]]
Sachin S
Я немного новичок с точки зрения Pythonic решений. Не могли бы вы или кто-нибудь из прохожих написать понимание списка в «итеративном подходе» в виде отдельных циклов?
Джонни Бой
4

Рекурсивный подход:

def rec_cart(start, array, partial, results):
  if len(partial) == len(array):
    results.append(partial)
    return 

  for element in array[start]:
    rec_cart(start+1, array, partial+[element], results)

rec_res = []
some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]  
rec_cart(0, some_lists, [], rec_res)
print(rec_res)

Итерационный подход:

def itr_cart(array):
  results = [[]]
  for i in range(len(array)):
    temp = []
    for res in results:
      for element in array[i]:
        temp.append(res+[element])
    results = temp

  return results

some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]  
itr_res = itr_cart(some_lists)
print(itr_res)
Jai
источник
3

Незначительная модификация вышеупомянутого рекурсивного генераторного решения в вариационном аромате:

def product_args(*args):
    if args:
        for a in args[0]:
            for prod in product_args(*args[1:]) if args[1:] else ((),):
                yield (a,) + prod

И, конечно, оболочка, которая заставляет его работать точно так же, как это решение:

def product2(ar_list):
    """
    >>> list(product(()))
    [()]
    >>> list(product2(()))
    []
    """
    return product_args(*ar_list)

с одним компромиссом : он проверяет, должна ли рекурсия прерываться на каждом внешнем цикле, и один выигрыш : нет выхода при пустом вызове, например product(()), что, я полагаю, будет семантически более правильным (см. doctest).

Что касается понимания списка: математическое определение применяется к произвольному числу аргументов, в то время как понимание списка может иметь дело только с известным числом из них.

Майк Лу
источник
2

Просто чтобы добавить немного к тому, что уже было сказано: если вы используете sympy, вы можете использовать символы, а не строки, что делает их математически полезными.

import itertools
import sympy

x, y = sympy.symbols('x y')

somelist = [[x,y], [1,2,3], [4,5]]
somelist2 = [[1,2], [1,2,3], [4,5]]

for element in itertools.product(*somelist):
  print element

О симпы .

Тайлер Хирс
источник
1

Я считаю, что это работает:

def cartesian_product(L):  
   if L:
       return {(a,) + b for a in L[0] 
                        for b in cartesian_product(L[1:])}
   else:
       return {()}
Ричард Самуэльсон
источник
0

Подход Стоунхенджа:

def giveAllLists(a, t):
    if (t + 1 == len(a)):
        x = []
        for i in a[t]:
            p = [i]
            x.append(p)
        return x
    x = []

    out = giveAllLists(a, t + 1)
    for i in a[t]:

        for j in range(len(out)):
            p = [i]
            for oz in out[j]:
                p.append(oz)
            x.append(p)
    return x

xx= [[1,2,3],[22,34,'se'],['k']]
print(giveAllLists(xx, 0))

вывод:

[[1, 22, 'k'], [1, 34, 'k'], [1, 'se', 'k'], [2, 22, 'k'], [2, 34, 'k'], [2, 'se', 'k'], [3, 22, 'k'], [3, 34, 'k'], [3, 'se', 'k']]
Сина
источник