Помогите мне с этой рекурсивной комбинаторной алгоритм

Question

Folks, У меня есть N ограниченные множества:

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

У меня есть функция f(), которая принимает один аргумент А из каждого набора:

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

I необходимо вызвать 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 products1 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) и так далее, пока не будут созданы все возможности. Запустите его на бумаге, чтобы увидеть, как это работает.

Дополнительный кредит: вы можете выяснить, как избавиться от параметра k?