代码之家 › 专栏 › 技术社区 › FMc TLP

当提供空列表时,itertools.product()应该生成什么?

cross-product itertools python

FMc TLP · 技术社区 · 14 年前

我想这是个学术问题,但第二个结果对我来说没有意义。难道它不应该像第一个一样完全空着吗?这种行为的基本原理是什么?

from itertools import product

one_empty = [ [1,2], [] ]
all_empty = []

print [ t for t in product(*one_empty) ]  # []
print [ t for t in product(*all_empty) ]  # [()]

更新

谢谢你所有的答案——非常有用。

维基百科关于 Nullary Cartesian Product 提供明确的声明:

没有集合的笛卡尔积… 单例集合是否包含空元组。

这里有一些代码,你可以用它来进行深入的研究 answer from sth :

from itertools import product

def tproduct(*xss):
    return ( sum(rs, ()) for rs in product(*xss) )

def tup(x):
    return (x,)

xs = [ [1, 2],     [3, 4, 5]       ]
ys = [ ['a', 'b'], ['c', 'd', 'e'] ]

txs = [ map(tup, x) for x in xs ]  # [[(1,), (2,)], [(3,), (4,), (5,)]]
tys = [ map(tup, y) for y in ys ]  # [[('a',), ('b',)], [('c',), ('d',), ('e',)]]

a = [ p for p in tproduct( *(txs + tys) )                   ]
b = [ p for p in tproduct( tproduct(*txs), tproduct(*tys) ) ]

assert a == b

2 回复 | 直到 12 年前

sth 12 年前

从数学的角度来看,没有元素的积应该产生操作的中性元素。产品不管是什么。

例如,对于整数,乘法的中性元素是一 ,因为 1αa= 对于所有整数一 . 所以整数的空积应该是一 . 当实现返回数字列表乘积的python函数时,自然会发生这种情况:

def iproduct(lst):
  result = 1
  for i in lst:
    result *= i
  return result

对于用该算法计算的正确结果, result 需要用初始化 1 . 这导致返回值为 一 当在空列表上调用函数时。

这个返回值对于函数的目的也是非常合理的。有了一个好的产品功能,您首先是合并两个列表,然后构建元素的产品,或者您首先构建两个单独列表的产品,然后将结果相乘,这都不重要:

iproduct(xs + ys) == iproduct(xs) * iproduct(ys)

如果 xs 或 ys 是空的,只有在 iproduct([]) == 1 .

现在更复杂了 product() 关于迭代器。从数学的角度来看, product([]) 应该返回该操作的中性元素,不管它是什么。它不是 [] 自从 product([], xs) == [] ,而对于中性元素 product([], xs) == xs 应该持有。但事实证明 [()] 也不是中性元素:

>>> list(product([()], [1,2,3]))
[((), 1), ((), 2), ((), 3)]

事实上, 产品() 实际上不是一个很好的数学产品,因为上面的公式不适用:

product(*(xs + ys)) != product(product(*xs), product(*ys))

产品的每一个应用程序都会生成一个附加的元组层,这是不可能的,因此甚至不可能有一个真正的中性元素。 [()] 不过,它并没有添加或删除任何元素,只是向每个元素添加一个空元组。

[()] 实际上,它是这个稍微经过调整的产品函数的中性元素,只对元组列表进行操作,但不会在每个应用程序上添加额外的元组层:

def tproduct(*xss):
  # the parameters have to be lists of tuples
  return (sum(rs, ()) for rs in product(*xss))

对于这个函数,上面的积方程成立:

def tup(x): return (x,)
txs = [map(tup, x) for x in xs]
tys = [map(tup, y) for y in ys]
tproduct(*(txs + tys)) == tproduct(tproduct(*txs), tproduct(*tys))

通过将输入列表打包成元组的附加预处理步骤, tproduct() 结果与 产品() 但从数学的角度来看,表现更好。而且它的中性元素是 [()] ,

所以 [()] 作为这种列表乘法的中性元素有一定的意义。即使它不完全适合 产品() 对于这个函数来说,它是一个很好的选择,因为例如,它允许定义 T生产() 无需为空输入引入特殊情况。

Mark Dickinson Alexandru 14 年前

正如@sth已经指出的,从数学的观点来看,这种行为是正确的。你真正需要说服自己的是 list(itertools.product()) 应该只有一个元素,因为一旦你知道了元素应该是什么:它必须是长度为0的元组,并且只有一个。

但元素的数量 itertools.product(l1, l2, l3, ...) 应该只是长度的乘积 l1 , l2 , l3 ,….so元素的数目 itertools.product() 应该是 empty product 也不缺少可以说服你空产品是1的网络资源。

我只是想指出这是正确的 实际的 定义以及正确的数学定义;也就是说,在边界情况下,定义最有可能“只起作用”。例如,假设要生成所有长度的字符串 n 由十进制数字组成,第一个数字非零。你可能会做如下的事情:

import itertools

def decimal_strings(n):
    """Generate all digit strings of length n that don't start with 0."""
    for lead_digit in '123456789':
        for tail in itertools.product('0123456789', repeat=n-1):
            yield lead_digit + ''.join(tail)

什么时候生产 n = 1 ?好吧,那样的话,你最后会打电话来 itertools.product 有空的产品( repeat = 0 )如果它什么也没有返回,那么内在的身体 for 上面的循环永远不会执行,所以 decimal_strings(1) 将是一个空的迭代器;几乎可以肯定不是您想要的。但自从 itertools.product('0123456789', repeat=0) 返回单个元组,得到预期结果:

>>> list(decimal_strings(1))
['1', '2', '3', '4', '5', '6', '7', '8', '9']

(什么时候 n = 0 当然,此函数会正确引发ValueError。)

所以简而言之,这个定义在数学上是合理的,而且往往不是你想要的。这绝对不是巨蟒虫!