如何迭代计算笛卡尔积？

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

我将继续进行递归。例如，在 fast&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 可以更好地完成工作，如 这个问题。）

Answer 1

1) 在各个列表中创建索引列表，初始化为 0，即：

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

2) 从每个列表中生成适当的元素（在本例中为第一个）。

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

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

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

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

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

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

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

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

未经测试，但该想法可行。希望我没有错过任何事情。

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

Answer 5

这个解决方案更长，但我发现它更容易理解，
首先，计算组成产品的组合数量（内部列表长度的乘法）
其次，循环组合数，组合数是可以解码为产品元素的唯一编码，

例如： [["Apple", "Orange"],[1,2,3], ..] -> 0 = [“苹果”, 1], 1 = [“苹果”, 2], 2 = [“苹果”, 3], 4 = [“橙色”, 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)