Help me with this recursive combinatorial algorithm

Question

Folks, I have N bounded sets:

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

I have a function f() that takes one argument A from each set:

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

I need to invoke f() for all possible combinations of arguments:

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

Can someone help me figure out a recursive (or iterative) algorithm that will hit all combinations?

Thanks in advance.

-Raj

Answer 1

So basically you want to generate the cartesian product s1 x s2 x ... x sN.

This is a classic application of backtracking / recursion. Here's how a pseudocode would look like:

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)

You should write it on paper and see how it works. For example, consider the sets:

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

The first call will be CartesianProduct({}, 1), which will then start iterating over the elements in the first set. The first recursive call with thus be CartesianProduct({1}, 2). This will go on in the same manner, eventually reaching CartesianProduct({1, 3, 5}, 4), for which the termination condition will be true (current.Length == N + 1). Then it will backtrack and call CartesianProduct({1, 3, 6}, 4) and so on, until all possibilities are generated. Run it on paper all the way to see exactly how it works. A

Extra credit: can you figure out how to get rid of the k parameter?