Kombinacje bez ponavljanja...

Funkcija kao argument prihvata neko polje (niz),
i cjelobrojni podatak (int k). Ona bi trebalo da vrati kombinacije bez ponavljanja k-te klase elemenata tog niza (ili bilo koje druge strukture - recimo vector<int>.) u nekom dvodimenzionalnom polju, ili da bude void ali da se polje za rezultat prenese kao argumenti.
Imam rijesenje ali me zanima dali i je moguce napisati funkciju a da nije rekurzivna. Odnosi se na one koji su mozda radili nesto slicno.

Pozdrav

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

Svaki rekurzivni problem može da se reši nerekurzivno.

Ovde je barem lako, jer se tačno zna koliko ima kombinacija k-te klase od n elemenata, pa bez problema možeš da upotrebiš najobičniju petlju.

Smatram da se bas ne radi o "najobicnijoj petlji" koja ide od 0 do N nad k. Cenim da mu za resenje treba dvostruka ili cak trostruka "nested" petlja. Ali, saznacemo :)

Naravno... Ali ne mora Nek napravi jednu petlju koja ide od 0 do (N nad k - 1) i u njoj poziva funkciju koja obavi ostatak

E ljudi hvala. Dovoljno mi je samo saznanje da se moze rijesiti.

Ako neko uradi ili ima uradjeno nek postuje.
Ja cu ako ova tema bude ziva postovati kod ako i kad zavrsim.

U svakom slucaju hvala.

Istina. Imas 13 pravila kako da rekurzivno pretvoris u nerekurzivno. Uzasno komplicirano...