我如何迭代地计算笛卡尔积？

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

我会使用递归。例如，在“快速脏” 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可以更好地完成此工作，就像这个问题中所述。）

- Federico A. Ramponi

Answer 1

1）创建一个索引列表，初始化为0，即：

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

2) 从每个列表中产生相应的元素（在本例中为第一个元素）。

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

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

请注意，这会以略微不同于您示例中的顺序输出结果。可以通过倒序迭代列表来修复此问题。

- Mark Byers

---

是的。确实很容易。谢谢。 - Federico A. Ramponi

我认为你的代码实际上比你的算法略微更低效.. ;P - Larry

是的...我有另一个版本，它与算法非常相似，但我认为它很混乱！也许我可以发布它... - Mark Byers

@Larry：我也发布了我的第一个版本！也许它可以写得更整洁一些，但它能用... - Mark Byers

只是说一下，因为当我提交我的答案并看到你的时候，你的显然更高效！ - Larry

使用模运算技巧的解决方案从第一个元素开始递增。 - norok2

Answer 2

既然您要求一种与语言无关的解决方案，这里有一个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 ...

- user unknown

Answer 3

对于所有的i，从0到\Pi a_i_length进行迭代。

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;  
    }
}

还有一些简单的方法可以编写代码，这样您就不必重复执行相同的工作。

- Larry

Answer 4

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

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;
  }
} 

没有测试过，但这个想法应该是可行的。希望我没有漏掉什么。

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

- IVlad

Answer 5

这个解决方案可能比较长，但我觉得更容易理解。 首先，计算组成产品的组合数（内部列表长度的乘积） 其次，循环遍历组合数，组合数是一种唯一的编码，您可以将其解码为产品元素

例如：[["Apple", "Orange"],[1,2,3], ..] -> 0 = ["Apple", 1]，1 = ["Apple", 2]，2 = ["Apple", 3]，4 = ["Orange", 1] ... 另一个例子：["Apple", 3] 等同于 [0, 2]

您可以将主列表中的每个元素视为数字，确定下一个数字的编码基数，因为第一个元素是 ["Apple", "Orange"]，它的大小为 2，所以第二个数字是 2 如果我们有：

[["Apple", "Orange"],[1,2,3], ["Shrimp", "Creep", "Sleep"]] 那么数字编码将是一个列表：[1, 2, 2*3]

from functools import reduce

def get_multiplication(digits: list):
    return reduce(lambda x, y: x*y, map(len, digits)) if digits else 1
    
def get_accumalated_multiplication(x: list[list]):
    return [get_multiplication(x[:i]) for i in range(len(x))]
    
def decode_to_product(encoding: int, encoding_digits: list, x: list):
    product = [0] * len(encoding_digits)
    current_product_encoding = encoding
    for i, digit in enumerate(reversed(encoding_digits)):
        bit = 0
        while ((bit + 1) * digit)  <= current_product_encoding:
            bit += 1 
        current_product_encoding -= digit * bit
        product[i] = x[i][bit]
    return tuple(product)
    

def product(x: list[list]):
    encoding_digits = get_accumalated_multiplication(x)
    num_products = reduce(lambda x, y: x*y, encoding_digits)

    for i in range(num_products):
        yield decode_to_product(i, encoding_digits, x)
    

- Tsvi Sabo