[Zadatak] funkija za permutacijeCode:
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;
}
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]
