摘要：问题描述：如何从一组列表中获取笛卡尔积（所有可能的值组合）？例如，给定somelists = [ [1, 2, 3], ['a', 'b'], [4, 5] ] 我如何获得它？[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, '...

问题描述：

如何从一组列表中获取笛卡尔积（所有可能的值组合）？

例如，给定

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努力解决这个问题，因为它要求每个输入序列都有单独的参数，而不是例如列表列表。接受的答案显示了如何使用来处理这个问题*。但是，在这里使用*来解包参数与在函数调用中使用它的其他任何时候都没有什么不同。请参阅本主题的将元组扩展为参数（并根据需要使用它来关闭重复的问题）。

解决方案 1：

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

解决方案 2：

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

解决方案 3：

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

解决方案 4：

我会使用列表理解：

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

解决方案 5：

使用itertools.product：

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

解决方案 6：

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

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

解决方案 7：

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

解决方案 8：

递归方法：

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_res = []
    for res in results:
      for element in array[i]:
        temp_res.append(res+[element])
    results = temp_res
  
  return results

some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]  
itr_res = itr_cart(some_lists)
print(itr_res)

解决方案 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]

Lambda 方法

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

解决方案 10：

对上面的递归生成器解决方案在可变参数方面稍作修改：

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(())，我认为这在语义上更正确（参见文档测试）。

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

解决方案 11：

您可以使用itertools.product标准库中的来获取笛卡尔积。其他很酷的相关实用程序itertools包括permutations、combinations和combinations_with_replacement。以下是以下代码片段的 Python CodePen链接：

from itertools import product

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

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

解决方案 12：

在 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 循环更灵活。

该代码基于PyPy 的 itertools.product 算法，该算法根据 MIT 许可证发布。

解决方案 13：

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

解决方案 14：

列表理解简单而清晰：

import itertools

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

解决方案 15：

这可以作为

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

解决方案 16：

如果你想自己重新实现它，你可以尝试使用递归。简单如下：

def product(cats, prefix = ()):
  if not cats:
    yield prefix
  else:
    head, *tail = cats
    for cat in head:
      yield from product(tail, prefix + (cat,))

是一个工作的开始。

递归深度是指您有多少个类别列表。

解决方案 17：

我喜欢上面的jack taylor的实现，因为它是迄今为止唯一一个可以轻松修改以流式传输答案而无需实现传入的迭代器的实现。所以，如果你正在做一堆非常大（或无限的，或昂贵的）迭代器的乘积，并且你可能会在结束之前停止，那么你只需要实现你需要的东西。

以下是修改它的一种方法：

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

    The interface is identical to itertools.product.
    """
    def index_from_stream(array_stream, index):
        try:
            while index >= len(array_stream[0]):
                next_element = next(array_stream[1])
                array_stream[0].append(next_element)

            return True, array_stream[0][index]

        except StopIteration:
            return False, None

    # Initialize data structures and handle bad input
    if len(args) == 0:
        # Match behavior of itertools.product
        yield ()
        return

    gears = [([], arg) for arg in args] * repeat
    for gear in gears:
        if not index_from_stream(gear, 0)[0]:
            return

    tooth_numbers = [0] * len(gears)
    result = [index_from_stream(gear, 0)[1] 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
            has_tooth, gear_tooth_value = index_from_stream(gear, tooth_number)
            if has_tooth:
                # No gear change is necessary, so exit the loop
                result[gear_number] = gear_tooth_value
                tooth_numbers[gear_number] = tooth_number
                break

            _, result[gear_number] = index_from_stream(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

解决方案 18：

我相信这是有效的：

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

解决方案 19：

以下代码 95% 是从使用 NumPy 构建两个数组的所有组合的数组中复制而来；所有功劳都归于那里！据说这要快得多，因为它只在 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)]

解决方案 20：

此处的代码比 itertools.product 快 6 倍，且占用的内存减少 10 倍。

它仅使用非常基本的运算符（中学编程课），这就是它如此高效的原因。

以下是我如何想到这个方法的解释

首先介绍一些背景知识：

您可能在学校/大学学习过二进制数，并做了很多练习，以便更轻松地理解这个系统。用一组有限的数字来引导会很奇怪，对吧？这意味着您已经创建了很多笛卡尔积，并且有一些很好的练习。

你用什么方法做到这一点的？

也许，你的老师告诉你主要使用这 3 个运算符：/ 和 % 和 *，这就是你所需要的（至少就我而言是这样的）。

我们来看一段代码和笛卡尔积对应的结果：

This code: product(range(0,5),range(0,7),range(0,8)) generates that: 


(0, 0, 0),
(0, 0, 1),
(0, 0, 2),
(0, 0, 3),
(0, 0, 4),
(0, 0, 5),
(0, 0, 6),
(0, 0, 7),
(0, 1, 0),
(0, 1, 1),
(0, 1, 2),
(0, 1, 3),
(0, 1, 4),
(0, 1, 5),
(0, 1, 6),
(0, 1, 7),
(0, 2, 0),
(0, 2, 1),
(0, 2, 2),
(0, 2, 3),
(0, 2, 4),
(0, 2, 5),
(0, 2, 6),
(0, 2, 7),
(0, 3, 0),
..

看起来几乎一样，对吧？几乎像二进制表。当我注意到这一点时，我感觉很有可能主要使用 / 和 % 和 * 来编写算法 - 没有递归，没有列表连接，没有生成器 - 什么都没有，只是 7 年级的计算机基础知识......

而且它出奇的简单。与二进制数据相比，唯一的区别是基数在每一列中经常变化 [输入数据的长度不同]。当达到第一个输入迭代器的长度 [ range(0,8) ] 时，第二列会突然开始，但不会像我们的十进制系统中那样从 8 开始。7 之后是 10，因为第一列的基数是 8 [ range(0,8) ]，。7 之后什么都没有了

(0, 0, 0),
(0, 0, 1),
(0, 0, 2),
(0, 0, 3),
(0, 0, 4),
(0, 0, 5),
(0, 0, 6),
(0, 0, 7),
(0, 1, 0),
(0, 1, 1),

再次查看代码：

现在，其他列的基数就变得非常清楚了。（如果不太清楚，请使用 len() ）

   (range(0,5),range(0,7),range(0,8))


And this is all what you need to get it going:

  from cython.parallel cimport prange
  cimport cython
  import numpy as np
  cimport numpy as np
  import cython
  ctypedef fused real:
      cython.char
  
      .... MORE DATA TYPES
      cython.longdoublecomplex
      cython.Py_hash_t
      cython.Py_UCS4
  cpdef void create_product(cython.Py_ssize_t liste, cython.Py_ssize_t[:] indlist, real[:] ctypesframedataresults, real[:] ear):
      cdef cython.Py_ssize_t geht,bleibt,zahlx,q,geht1,zahl
      cdef cython.Py_ssize_t indlistlen =len(indlist)
      for q in prange(liste,nogil=True):
          geht = q
          bleibt = 0
          for zahlx in range(indlistlen):
              zahl=indlist[zahlx]
              geht1 = geht // zahl # 8th grade - computer science class - the heart of the algorithm :)
              bleibt = geht % zahl
              geht = geht1
              ctypesframedataresults[q*indlistlen+zahlx] = ear[bleibt] # this was a little tricky,

这里是 Python 代码（比算法更高级 :-) ）：

    import functools
    import operator
    from collections import defaultdict
    from cythonproduct import create_product #import the compiled file
    import numpy as np
    
    def get_pointer_array(original):
        dty = np.ctypeslib.as_ctypes_type(original.dtype)
    
        b = original.ctypes.data
        buff = (dty * original.size).from_address(b)
    
        aflat = np.frombuffer(buff, dtype=original.dtype)
        return aflat
    
    def  cartesian_product(*args):
        lookup1 = {}
        lookup2 = defaultdict(list)
        i = 0
        # Create dictionaries for indexing and lookup during computation
        for arg in (args):
            for f in arg:
                lookup2[f].append(i)
                lookup1[i] = f
                i += 1
    
        indlist = np.array([len(x) for x in args],dtype=np.int64) # get the bases
        listexx = int(np.product(indlist)) # shape of output array (1 column)
        dty = np.array(list(lookup2.keys()))
        rightshape = np.array(functools.reduce(operator.add, list(lookup2.values())))
        bestdtype = (dtypecheck(dty, filterna=False, float2int=False, )) # optional - you can use your own
        # this part is used to create a numpy array that serves as a lookup dict (without hashing anything) - to that we can use all kind of values, not only 0,1,2,3,4,5...
        ear = np.zeros(rightshape.shape, dtype=bestdtype.dtype)
        for k, item in lookup1.items(): # with numpy arrays, we can disable the GIL.
            ear[k] = item # (Only a few elements - for is ok)
        dataresults = np.zeros((listexx, len(indlist)), dtype=ear.dtype)
        if not dataresults.flags['C_CONTIGUOUS']: # may not be necessary, but who knows …
            dataresults = np.ascontiguousarray(dataresults)
        # this is how you get a pointer. I don't know if there are better/safer ways (Strides maybe?)
        # Ctypes works, that is what counts. We can modify the flat array in Cython and see the results in the
        # ndim array. That way, we can pass anything to Cython. And  we can loop in Cython like
        # we would in Python (almost) using .... guess what: the Cartesian product. You can generate
        # the product on the Python side, pass the index array (always 2D) and use it as a loop index on the
        # Cython site, and no function signature will ever bother you.
        ctypesframedataresults = get_pointer_array(dataresults)
        # Let Cython do the work here and modify the memory directly. There is probably nothing in this world
        # the uses more memory than a Cartesian product :)
        create_product(listexx, indlist, ctypesframedataresults, ear)
        return dataresults
    
I posted an auto-compiling version on GitHub, in case that you want to use it, but don't know how to configure Cython: https://github.com/hansalemaos/cythoncartesian/blob/main/__init__.py

基准



Benchmark: 

args2=[list(range(8)),list(range(8)),list(range(8)),list(range(8)),
      list(range(8)),list(range(8)),list(range(8)),list(range(8)),
      list(range(8))]

dataresults=cartesian_product(*args2)
      

# Mem usage 2 GB
# Out[4]:
# array([[0, 0, 0, ..., 0, 0, 0],
#        [1, 0, 0, ..., 0, 0, 0],
#        [2, 0, 0, ..., 0, 0, 0],
#        ...,
#        [5, 7, 7, ..., 7, 7, 7],
#        [6, 7, 7, ..., 7, 7, 7],
#        [7, 7, 7, ..., 7, 7, 7]], dtype=uint8)
# %timeit dataresults=cartesian_product(*args2)
# 2.65 s ± 163 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# dataresults.shape
# Out[6]: (134217728, 9)

Itertools:

itertools.product

Mem usage 16 GB

import itertools

%timeit (list(itertools.product(*args2)))

11.5 s ± 203 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

By the way: it is also extremely fast without Cython, but I haven't done a benchmark yet.

如何获取多个列表的笛卡尔积