如何迭代计算笛卡尔积？

Question

这个问题询问如何计算给定数量向量的笛卡尔乘积.由于向量的数量是预先知道的并且相当小,因此使用嵌套的for循环很容易获得解决方案.

现在假设您以您选择的语言给出了向量(或列表列表或集合等)的向量:

l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ]

如果我被要求计算其笛卡尔积,那就是

[ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ]

我会继续递归.例如,在快速和肮脏的python中,

def cartesianProduct(aListOfLists):
    if not aListOfLists:
        yield []
    else:
        for item in aListOfLists[0]:
            for product in cartesianProduct(aListOfLists[1:]):
                yield [item] + product

有一种简单的方法可以迭代计算它吗？

(注意:答案不需要在python中,无论如何我都知道在python中,itertools可以更好地完成工作,就像在这个问题中一样.)

Answer 1

1)在相应列表中创建索引列表,初始化为0,即:

indexes = [0,0,0,0,0,0]

2)从每个列表中产生适当的元素(在这种情况下是第一个).

3)将最后一个索引加1.

4)如果最后一个索引等于最后一个列表的长度,则将其重置为零并携带一个.重复此操作,直到没有进位.

5)回到第2步,直到索引回到[0,0,0,0,0,0]

它类似于计数的工作原理,除了每个数字的基数可以不同.

以下是Python中上述算法的实现:

def cartesian_product(aListOfList):
    indexes = [0] * len(aListOfList)
    while True:
        yield [l[i] for l,i in zip(aListOfList, indexes)]
        j = len(indexes) - 1
        while True:
            indexes[j] += 1
            if indexes[j] < len(aListOfList[j]): break
            indexes[j] = 0
            j -= 1
            if j < 0: return

这是使用模数技巧实现它的另一种方法:

def cartesian_product(aListOfList):
    i = 0
    while True:
        result = []
        j = i
        for l in aListOfList:
             result.append(l[j % len(l)])
             j /= len(l)
        if j > 0: return
        yield result
        i += 1

请注意,这会以与示例中略有不同的顺序输出结果.这可以通过以相反的顺序迭代列表来修复.