帮我解决这个递归组合算法

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 )

有人能帮我找出一种递归（或迭代）算法吗？会击中所有组合吗？

提前致谢。

-拉吉

Answer 1

所以基本上你想生成 笛卡尔积 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)，其终止条件将为 true (current.Length == N + 1）。然后回溯并调用CartesianProduct({1, 3, 6}, 4)等等，直到生成所有可能性。在纸上一路运行它，看看它到底是如何工作的。

额外加分：你能弄清楚如何去掉k参数吗？