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

输入:

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可以很好地处理这个问题。参见对列表中的每对元素的操作或生成具有重复的排列。


当前回答

这可以用

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

其他回答

在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许可下发布的。

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

列表推导式简单明了:

import itertools

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

出现使用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)

我相信这是可行的:

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