13

这个问题询问如何计算给定数量向量的笛卡尔积。由于向量的数量是预先知道的并且相当少，因此使用嵌套的 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 做得更好，就像在这个问题中一样。）

4

4 回答 4

21

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

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

于 2010-03-10T18:14:24.887 回答
3

既然您要求一种与语言无关的解决方案，这里是 bash 中的一个，但我们可以称它为迭代、递归，它是什么？这只是符号：

echo {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 1,4,6,10,11,13 ...
于 2011-03-03T06:25:33.603 回答
2

从 0 迭代到\Pi a_i_lengthfor all i。

for ( int i = 0; i < product; i++ ) {
    // N is the number of lists
    int now = i;
    for ( int j = 0; j < N; j++ ) {
        // This is actually the index, you can get the value easily.
        current_list[j] = now % master_list[j].length;

        // shifts digit (integer division)
        now /= master_list[j].length;  
    }
}

还有一些简单的方法可以写这个，所以你不必做同样的工作两次。

于 2010-03-10T18:20:35.037 回答
1

你只需要手动管理你的堆栈。基本上，做你自己做的递归。由于递归将有关每个递归调用的数据放在堆栈上，因此您只需执行相同操作：

Let L[i] = elements in vector i
k = 0;
st[] = a pseudo-stack initialized with 0
N = number of vectors 
while ( k > -1 )
{
  if ( k == N ) // solution, print st and --k

  if ( st[k] < L[k].count )
  {
    ++st[k]
    ++k
  }
  else
  {
    st[k] = 0;
    --k;
  }
}

未经测试，但这个想法会奏效。希望我没有错过任何东西。

编辑：好吧，我猜为时已晚。这与计数基本相同，只是另一种看待它的方式。

于 2010-03-10T18:31:12.770 回答