如何从一组列表中得到笛卡尔积(每一种可能的值组合)?
输入:
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可以很好地处理这个问题。参见对列表中的每对元素的操作或生成具有重复的排列。
当前回答
在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)。
其他回答
在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许可下发布的。
对上面的递归生成器解决方案做了一个可变风格的小修改:
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，例如product(())，我认为这在语义上更正确(参见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)
在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。用标准库中的积来得到笛卡尔积。itertools中其他很酷的相关实用程序包括排列、组合和combinations_with_replacement。下面是一个python代码片段的链接:
from itertools import product
somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
result = list(product(*somelists))
print(result)
