algorithm - 如何迭代计算笛卡尔积？

Question

This 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], ... ]

我会继续递归。例如，在 quick&dirty 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 做得更好，如 this question。)

Answer 1

1)创建一个索引列表到各自的列表中，初始化为0，即:

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

2) 从每个列表中产生适当的元素(在本例中是第一个)。

3) 将最后一个索引增加一个。

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

请注意，这会以与示例中略有不同的顺序输出结果。这可以通过以相反顺序遍历列表来解决。