如何从一组列表中得到笛卡尔积(每一种可能的值组合)?
输入:
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可以很好地处理这个问题。参见对列表中的每对元素的操作或生成具有重复的排列。
当前回答
下面的代码是使用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')]
Out:
[(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)]
其他回答
下面的代码是使用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')]
Out:
[(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)]
虽然已经有很多答案，但我想分享一些我的想法:
迭代方法
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)
你可以使用itertools。用标准库中的积来得到笛卡尔积。itertools中其他很酷的相关实用程序包括排列、组合和combinations_with_replacement。下面是一个python代码片段的链接:
from itertools import product
somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
result = list(product(*somelists))
print(result)
出现使用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 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)
