如何迭代计算笛卡尔积？

小编典典

如何迭代计算笛卡尔积？

algorithm

这个问题问如何计算给定数量的向量的笛卡尔积。由于向量的数量是事先已知的，并且很小，因此，使用嵌套的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可以更好地完成此工作

阅读 277

2020-07-28

共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

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

2020-07-28