[ boris Dj.bl @ 05.10.2008. 13:19 ] @
Evo jedna mala funkcija 'next' koja daje sledecu permutaciju niza brojeva. Code: void next(int[] a,int n) { int k,j,r,s; k = n-1; while (a[k] > a[k+1]) k--; j = n; while (a[k] > a[j]) j--; swap(j,k,a); r = n; s = k+1; while (r>s) { swap(r,s,a); r--; s++; } } void swap(int i, int j,int[] a) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } Npr ako imamo skup S={1,2,3} permutacije (bez ponavljanja) su redom 123 132 213 231 321 312 Neka imamo niz[]={0,1,2,3} i n=3 onda svakim pozivanjem funkcije next(niz,3) ovaj niz se promjeni i postane sledeca permutacija. (u nizu mora postojati prvi element 0) al ce permutacija biti samo elementi niz[1], niz[2],...,niz[n] pa je ovdje niz[1]=1, niz[2]=2,niz[3]=3 a poslije prve permutacije ce biti niz[1]=1, niz[2]=3,niz[3]=2 itd Npr za n=5 niz[]={0,1,2,3,4,5} E sad mene zanima ako neko zna da objasni kako tacno radi ovaj algoritam. Naime skontao sam da se krene sa kraja niza ulijevo i trazi se prvi broj manji od predzadnjeg i da onda oni zamijene mjesta. Zatim se krene od tog opet udesno a od zadnjeg ulijevo i dok god je trenutni lijevi veci od trenutnog desnog mjenjaju mjesta a cim ne se naidje na prvi manji prekida se. Mene samo zanima po kojoj logica ovo radi ( a zaista radi ) jer nisam bas potpuno skontati. Pa ako neko zna da pojasni ... [Ovu poruku je menjao boris Dj.bl dana 05.10.2008. u 15:24 GMT+1] |