帮我实现这个递归组合算法

Question

朋友们，我有N个有界集：

S1 = {s11, s12, ... s1a }
S2 = {s21, s22, ... s2b }
...
sN=  {sN1, sN2, ... sNx }

我有一个函数f()，它从每个集合中接受一个参数A：

f( A1, A2, ... AN ) such that Ax belongs to Sx

我需要为所有可能的参数组合调用f()：

f( s11, s21, ... sN1 )
f( s11, s21, ... sN2 )
f( s11, s21, ... sN3 )
...
f( s11, s21, ... sNx )
...
f( s1a, s2b, ... sNx )

有人能帮我找出一种递归(或迭代)算法，可以处理所有组合吗？

提前谢谢。

-Raj

Answer 1

所以基本上您想要生成cartesian product s1 x s2 x ... x sN。

这是一个经典的回溯/递归应用。下面是伪代码的样子：

function CartesianProduct(current, k)
    if (k == N + 1)
        current is one possibility, so call f(current[1], current[2], ..., current[N])
        and return

    for each element e in Sk
        call CartesianProduct(current + {e}, k + 1)

Initial call is CartesianProduct({}, 1)

你应该把它写在纸上，看看它是如何工作的。例如，考虑以下集合：

s1 = {1, 2}
s2 = {3, 4}
s3 = {5, 6}

第一个调用将是CartesianProduct({}, 1)，然后它将开始迭代第一个集合中的元素。因此，第一个递归调用是CartesianProduct({1}, 2)。这将以相同的方式进行，最终到达CartesianProduct({1, 3, 5}, 4)，其终止条件将为真(current.Length == N + 1)。然后，它将回溯并调用CartesianProduct({1, 3, 6}, 4)，依此类推，直到生成所有可能性。在纸上运行它，看看它到底是如何工作的。一个

Extra credit：你能想出怎么去掉k参数吗？