如何得到一系列表的笛卡尔积

如何从一组列表中得到笛卡尔积(每一种可能的值组合)?

输入:

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循环获得更具体的重复。

如果你想要一个相同的列表与自身多次相乘的笛卡尔积，itertools.product可以很好地处理这个问题。参见对列表中每对元素的操作或生成重复排列。

330948 次浏览
小开
最佳答案

使用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)
>>>
小开

itertools.product:

import itertools
result = list(itertools.product(*somelists))
小开

在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)。

小开

对于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())
[()]
小开

这是一个递归生成器，它不存储任何临时列表

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)]
小开

只是补充一点已经说过的:如果你使用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

关于sympy。

小开

我会使用列表推导式:

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]]
小开

对上面的递归生成器解决方案做了一个可变风格的小修改:

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)

一个权衡:它检查递归是否应该在每个外部循环中中断，而一个获得:在空调用时不产生yield，例如__abc0，我认为这在语义上更正确(参见doctest)。

关于列表推导式:数学定义适用于任意数量的参数，而列表推导式只能处理已知数量的参数。

小开

虽然已经有很多答案，但我想分享一些我的想法:

迭代方法

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]

Lambda方法

def cartesian_reduct(pools):
return reduce(lambda x,y: product(x,y) , pools)
小开

递归的方法:

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)
小开

我相信这是可行的:

def cartesian_product(L):
if L:
return {(a,) + b for a in L[0]
for b in cartesian_product(L[1:])}
else:
return {()}
小开

你可以在标准库中使用itertools.product来获得笛卡尔积。itertools中其他很酷的相关实用程序包括permutations、combinations和combinations_with_replacement。下面是一个链接对下面代码片段的python代码依赖:

from itertools import product


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


result = list(product(*somelists))
print(result)
小开

下面的代码是从使用numpy构建两个数组的所有组合的数组复制的95%，所有的学分都在那里!据说这要快得多，因为它只使用numpy格式。

import numpy as np


def cartesian(arrays, dtype=None, out=None):
arrays = [np.asarray(x) for x in arrays]
if dtype is None:
dtype = arrays[0].dtype
n = np.prod([x.size for x in arrays])
if out is None:
out = np.zeros([n, len(arrays)], dtype=dtype)


m = int(n / arrays[0].size)
out[:,0] = np.repeat(arrays[0], m)
if arrays[1:]:
cartesian(arrays[1:], out=out[0:m, 1:])
for j in range(1, arrays[0].size):
out[j*m:(j+1)*m, 1:] = out[0:m, 1:]
return out

如果不希望对所有条目使用第一个条目的dtype，则需要将dtype定义为参数。如果有字母和数字作为项，则采用dtype = 'object'。测试:

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


[tuple(x) for x in cartesian(somelists, 'object')]

:

[(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)]
小开

这可以用

[(x, y) for x in range(10) for y in range(10)]

另一个变量?没有问题:

[(x, y, z) for x in range(10) for y in range(10) for z in range(10)]
小开

列表推导式简单明了:

import itertools


somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
lst = [i for i in itertools.product(*somelists)]
小开

在99%的情况下，你应该使用itertools.product。它是用高效的C代码编写的，因此它可能比任何自定义实现都要好。

在1%的情况下，您需要只使用python算法(例如，如果您需要以某种方式修改它)，您可以使用下面的代码。

def product(*args, repeat=1):
"""Find the Cartesian product of the arguments.


The interface is identical to itertools.product.
"""
# Initialize data structures and handle bad input
if len(args) == 0:
yield () # Match behavior of itertools.product
return
gears = [tuple(arg) for arg in args] * repeat
for gear in gears:
if len(gear) == 0:
return
tooth_numbers = [0] * len(gears)
result = [gear[0] for gear in gears]


# Rotate through all gears
last_gear_number = len(gears) - 1
finished = False
while not finished:
yield tuple(result)


# Get next result
gear_number = last_gear_number
while gear_number >= 0:
gear = gears[gear_number]
tooth_number = tooth_numbers[gear_number] + 1
if tooth_number < len(gear):
# No gear change is necessary, so exit the loop
result[gear_number] = gear[tooth_number]
tooth_numbers[gear_number] = tooth_number
break
result[gear_number] = gear[0]
tooth_numbers[gear_number] = 0
gear_number -= 1
else:
# We changed all the gears, so we are back at the beginning
finished = True

接口与itertools.product相同。例如:

>>> list(product((1, 2), "ab"))
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

这个算法相对于本页上其他只使用python的解决方案有以下优点:

  • 它不会在内存中建立中间结果，从而保持较小的内存占用。
  • 它使用迭代而不是递归，这意味着你不会得到“最大递归深度超出”。错误。
  • 它可以接受任意数量的输入可迭代对象，这使得它比使用嵌套的for循环更灵活。

此代码基于itertools。来自PyPy的乘积算法，即根据MIT许可证发布。


提交答案