如何迭代地计算笛卡尔积? [英] 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屋！