|
dragansm
Dragan Smiljanic
Član broj: 38170
Poruke: 191
212.200.125.*
|
Jeste mozda malo vise "cimanja" napisati algoritam, ali resenje je u sustini jednostvni i pokusacu da ga "skiciram".
Posmatracemo kombinacije bez ponavljanja N elemenata P k-tog reda ili klase.
Napravi niz od k elemenata koji sadrzi indexe elmenata (idx).
idx[m] = m, m = 0 .. (k - 1)
rez[0] = Komb( idx )
while( idx[k-1] != N )
++idx[k-1]
rez[..] = Komb( idx )
end_while
++idx[k - 2]
idx[k - 1] = idx[k-2]+1
Ako je idx[k-2] != N - 1 vrati se u gornju petlju
++idx[k - 3]
idx[k-2] = idx[k-3]+1
idx[k-1] = idx[k-2]+1
Ako je idx[k-3] != N - 2 vrati se u gornju petlju
.....
Komb( idx ) vraca vektor (P[idx[0]], P[idx[1]],... P[idx[k - 1]])
Nadam se da ti je ideja jasna i da ti nece biti problem da je pretvoris u lepu citku C/C++ funkciju prigodnu za ovaj forum, mada verujem da je interesantno i tvoje rekurzivno resenje.
Za P = {A,B,C,D} i k = 2 bi trebalo da se dobije
AB, AC, AD, BC, BD, CD
Bitno je da dobro postavis uslov kad izlazis iz funkcije, a to je situacija kad je idx[0] == N - k - 1 ili tako neka vrednost koja linearno zavisi od N, k i konstante (nece ti biti problem da je sam odredis)
By the Way, ortak sa posla mi je ispricao da je nasao negde da je matem. dokazano da svaku rekur. funkciju mozes da resis bez rekurzije koriscenjem iteracije, ali ne znam link za taj sajt, gde je navodno i objasnjen sam princip kako pretvarati jedne funkcije u druge.
Pozdrav
|
Kombinacje bez ponavljanja...
Nek napravi jednu petlju koja ide od 0 do (N nad k - 1) i u njoj poziva funkciju koja obavi ostatak 
