Помоги мне с этим рекурсивным комбинаторным алгоритмом - PullRequest
Новая
       14

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

2 голосов
/ 02 января 2011

Ребята, у меня 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

1 Ответ

3 голосов
/ 02 января 2011

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

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

...