Sve moguce kombinacije niza brojeva duzine n

[ Sale_123 @ 21.05.2004. 10:02 ] @

Cao. Zapeo sam na jednom zadtku sa stringovima ali da bi ga rijesio trebam naci sve moguce kombinacije niza brojeva duzine n.

Npr. n=4
1 2 3 4
Kombinacije su:
1,12,123,1234,13,134,14,2,23,234,24,3,34,4

[ srki @ 21.05.2004. 15:54 ] @

Mozes da resis na nekoliko nacina. Npr. mozes rekurzijom tako sto imas neki globalni temporary string a duzinu tog strina prosledjujes rekurzivnoj funkciji kao i polozaj karaktera u pocetnom stringu za koji gledas da li da ga ubacis ili ne uvacis. Prvi put pozoves kombinacije(0,0) (j=0, k =0)
a ta funkcija ce da ti uradi ovo

if (k<n)

{
temp[j]=zadati_string[k];
kombinacije(j+1,k+1); //ubacili smo trenutni karakter u nasu kombinaciju
kombinacije(j,k+1); // nismo ubacili.....
}
else
temp[j]=0;
cout << temp;

Postoji i nerekurzivni nacin. Evo ovo ce da ti pomogne.
Imas string aghw
uzmes broj k koji ces da postavis na nulu. Sada gledas njegova poslednja 4 bita. Kada je neki bit postavljen na 1 onda odstampas odgovarajuci karakter a u suprotnom ne stampas.
Recimo povecas k za 1. Onda ce da ti se odstampa w
povecas ponovo k za 1 i k ce biti 2 a binarno 0010 i odtampaces h
povecas ponovo k za 1 i k ce biti 2 a binarno 0011 i odstampaces hw
itd...

onda bi ti program izgledao ovako
for k:=1 to (2^n)-1 do
begin
odstampaj odgovarajuce karaktere
odstampaj novi red
end

[ blaza @ 21.05.2004. 16:27 ] @

Izmena: Skratio sam kod.

Code:

#include <iostream>
using namespace std;

int m;

void prikazi(int j = 0, int n = 0){
    static int niz[20] = {0};
    niz[n++] = j;
    for (int k = 1; k < n; k++)
        cout << niz[k];
    cout << " ";
    for (k = j + 1; k <= m; k++)
        prikazi(k, n);
}

int main(int argc, char** argv){
    cout << "Koliko (<19)?";
    cin >> m;
    prikazi();
    return 0;
}

[ Sale_123 @ 23.05.2004. 21:16 ] @

Hvala vam mnogo. Zadatak sam uspio rijesiti ugradjujuci svoj kod u vas ali i dalje mi ostala nejasan onaj primjer sa rekurijom. A sto se tice onih ideja sa bitovima, nema se sta reci, ideja je odlicna.