如何迭代计算笛卡尔积? [英] How can I compute a Cartesian product iteratively?

问题描述

这个问题询问如何计算给定数量向量的笛卡尔积.由于向量的数量是预先知道的，而且数量很少，所以用嵌套的 for 循环很容易得到解决方案.

This question asks how to compute the Cartesian product of a given number of vectors. Since the number of vectors is known in advance and rather small, the solution is easily obtained with nested for loops.

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

Now suppose that you are given, in your language of choice, a vector of vectors (or list of lists, or set of sets, etc.):

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

如果我被要求计算它的笛卡尔积，那就是

If I was asked to compute its Cartesian product, that is

[ [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中，

I would proceed with recursion. For example, in 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

有没有一种简单的方法来迭代计算它?

Is there an easy way to compute it iteratively?

(注意:答案不需要在 python 中，无论如何我知道在 python 中 itertools 做得更好，如 这个问题.)

(Note: The answer doesn't need to be in python, and anyway I'm aware that in python itertools does the job better, as in this question.)

推荐答案

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

1) Create a list of indexes into the respective lists, initialized to 0, i.e:

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

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

2) Yield the appropriate element from each list (in this case the first).

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

3) Increase the last index by one.

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

4) If the last index equals the length of the last list, reset it to zero and carry one. Repeat this until there is no carry.

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

5) Go back to step 2 until the indexes wrap back to [0,0,0,0,0,0]

这与计数的工作原理类似，只是每个数字的基数可以不同.

It's similar to how counting works, except the base for each digit can be different.

以上算法在 Python 中的实现:

Here's an implementation of the above algorithm in 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

<小时>

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

---

Here is another way to implement it using modulo tricks:

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

请注意，这会以与您的示例略有不同的顺序输出结果.这可以通过以相反的顺序迭代列表来解决.

Note that this outputs the results in a slightly different order than in your example. This can be fixed by iterating over the lists in reverse order.

这篇关于如何迭代计算笛卡尔积?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！