| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Gost
|
 Postano: 11:44 sub, 1. 1. 2005 Naslov: Particioniranje multiskupa |
    |
|
|
Zanima me kako na sve moguce nacine particionirati dani multiskup na dvije (neuredjene - dakle isto je {{1},{1,2}} i {{1,2},{1}}) particije tako da svaka particija ima barem jedan element. Treba mi konkretna procedura (sto efikasniji algoritam) a ne samo broj takvih particija.
Za one koji ne znaju: multiskup je kolekcija elemenata ciji poredak je nevazan a koji medjusobno ne moraju nuzno biti razliciti.
(Dakle {1,1,2} i {1,1,1,2} su dva razlicita multiskupa, prvi kardinaliteta 3, drugi 4)
Meni je prva ideja bila da idem po kardinalnom broju prve particije (druga se uvijek lako dobije komplementiranjem)... za k=1 je jednostavno, treba samo uzeti sve razlicite elemente, vec za k=2 nastaju mali problemi... Treba proci po svim razlicitim prvim elementima, te uzeti sve druge elemente (pazeci da ne dobijemo dva ista multiskupa; dakle ok, neka bude sortiran polazni multiskup pa cemo u drugoj petlji proci jednom sve medjusobno razlicite i >= prvom) Za k=3 treba uzeti sve moguce kombinacije iz k=2 i pridodati im novi... Drugim rijecima imamo slozenost O(n^3), a ocito je da imamo neke stvari redundantne jer pri svakom vecem k mi ponovno konstruiramo multiskupice koje smo sve vec konstruirali za k-1.
Dakle zakljucak toga je da treba ici po (medjusobno razlicitim) elementima. Za prvu particiju (card >0, <=n/2) uzmemo na sve moguce nacine prvi element (opet pretpostavimo da imamo sortiran polazni multiskup, pa je to jedna linearna setnja) i onda s njim pokusamo realizirati sve moguce kombinacije... dodamo prazan skup, pa sve moguce multipodskupove polaznog iz kojeg smo izvadili prvi (sada kardinaliteta >0, <=n/2-1), sto je zapravo smanjeni polazni problem. Dakle imamo rekurziju u kojoj prenosimo kao argumente citave multiskupove (koji mogu biti veliki) sto mi se opet bas ne svidja.
Ima li sta efikasnije i elegantnije??
Please ljudi, hitno mi je, tako da cu biti zahvalan na svakoj ideji.
Zanima me kako na sve moguce nacine particionirati dani multiskup na dvije (neuredjene - dakle isto je {{1},{1,2}} i {{1,2},{1}}) particije tako da svaka particija ima barem jedan element. Treba mi konkretna procedura (sto efikasniji algoritam) a ne samo broj takvih particija.
Za one koji ne znaju: multiskup je kolekcija elemenata ciji poredak je nevazan a koji medjusobno ne moraju nuzno biti razliciti.
(Dakle {1,1,2} i {1,1,1,2} su dva razlicita multiskupa, prvi kardinaliteta 3, drugi 4)
Meni je prva ideja bila da idem po kardinalnom broju prve particije (druga se uvijek lako dobije komplementiranjem)... za k=1 je jednostavno, treba samo uzeti sve razlicite elemente, vec za k=2 nastaju mali problemi... Treba proci po svim razlicitim prvim elementima, te uzeti sve druge elemente (pazeci da ne dobijemo dva ista multiskupa; dakle ok, neka bude sortiran polazni multiskup pa cemo u drugoj petlji proci jednom sve medjusobno razlicite i >= prvom) Za k=3 treba uzeti sve moguce kombinacije iz k=2 i pridodati im novi... Drugim rijecima imamo slozenost O(n^3), a ocito je da imamo neke stvari redundantne jer pri svakom vecem k mi ponovno konstruiramo multiskupice koje smo sve vec konstruirali za k-1.
Dakle zakljucak toga je da treba ici po (medjusobno razlicitim) elementima. Za prvu particiju (card >0, <=n/2) uzmemo na sve moguce nacine prvi element (opet pretpostavimo da imamo sortiran polazni multiskup, pa je to jedna linearna setnja) i onda s njim pokusamo realizirati sve moguce kombinacije... dodamo prazan skup, pa sve moguce multipodskupove polaznog iz kojeg smo izvadili prvi (sada kardinaliteta >0, <=n/2-1), sto je zapravo smanjeni polazni problem. Dakle imamo rekurziju u kojoj prenosimo kao argumente citave multiskupove (koji mogu biti veliki) sto mi se opet bas ne svidja.
Ima li sta efikasnije i elegantnije??
Please ljudi, hitno mi je, tako da cu biti zahvalan na svakoj ideji.
|
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
| Postano: 19:41 sub, 1. 1. 2005 Naslov: |
|
|
nisi bas napisao ogranicenja, koliko razlicitih elemenata moze biti, etc.
no, dobro.
za pocetak napises multiskup onako kako se multiskup zapisuje ;)
a1^x1 a2^x2... an^xn, gdje su a1..an razliciti elementi multiskupa, x1..xn broj ponavljanja istih.
napravis polje od N elemenata u koje ces zapisivati koliko si istih elemenata uzeo i rekurziras kroz to.
npr multiskupich aabbbc ce biti prvo zapisan kao 2, 3, 1 u tom nizu, N = 3.
i sad rekurzija koja ide do dubine N i uzima 0..xi elemenata (i je trenutna dubina - tj. polozaj u nasem nizu).
evo neka jednostavna implementacija tog primjera sa skupom aabbbc
[code:1]
void rek (int *a, int *b, int x, int n) {
int i, j;
if (x==n) { /*kada smo izgenerirali sve razlicite elemente, ispisemo sto smo generirali*/
for (i=0;i<n;i++)
for (j=0;j<b[i];j++)
printf("%c", i+'a');
printf(" ");
for (i=0;i<n;i++)
for (j=b[i];j<a[i];j++)
printf("%c", i+'a');
printf("\ n");
return; /* i onda ubijemo rekurziju */
}
for (i=0;i<=a[x];i++) { /* za prvi skup mozemo uzeti bilokoji broj elemenata, ukljucno sa nulom */
b[x]=i;
rek(a, b, x+1, n);
}
}
int main () {
int a[3], b[3];
/* u a se nalazi koliko kojih elemenata imamo u multiskupu
u b ce se nalaziti trenutna particija multiskupa */
a[0]=2;
a[1]=3;
a[2]=1;
rek(a, b, 0, 3);
return 0;
}
[/code:1]
tu se dalje moze svasta raditi. svatis elemente skupova kao proste brojeve, pa ti je zapravo skup isto sto i neki slozeni broj, te mu nadjes sve djelitelje...
no, dobro.
za pocetak napises multiskup onako kako se multiskup zapisuje ;)
a1^x1 a2^x2... an^xn, gdje su a1..an razliciti elementi multiskupa, x1..xn broj ponavljanja istih.
napravis polje od N elemenata u koje ces zapisivati koliko si istih elemenata uzeo i rekurziras kroz to.
npr multiskupich aabbbc ce biti prvo zapisan kao 2, 3, 1 u tom nizu, N = 3.
i sad rekurzija koja ide do dubine N i uzima 0..xi elemenata (i je trenutna dubina - tj. polozaj u nasem nizu).
evo neka jednostavna implementacija tog primjera sa skupom aabbbc
| Kod: |
void rek (int *a, int *b, int x, int n) {
int i, j;
if (x==n) { /*kada smo izgenerirali sve razlicite elemente, ispisemo sto smo generirali*/
for (i=0;i<n;i++)
for (j=0;j<b[i];j++)
printf("%c", i+'a');
printf(" ");
for (i=0;i<n;i++)
for (j=b[i];j<a[i];j++)
printf("%c", i+'a');
printf("\n");
return; /* i onda ubijemo rekurziju */
}
for (i=0;i<=a[x];i++) { /* za prvi skup mozemo uzeti bilokoji broj elemenata, ukljucno sa nulom */
b[x]=i;
rek(a, b, x+1, n);
}
}
int main () {
int a[3], b[3];
/* u a se nalazi koliko kojih elemenata imamo u multiskupu
u b ce se nalaziti trenutna particija multiskupa */
a[0]=2;
a[1]=3;
a[2]=1;
rek(a, b, 0, 3);
return 0;
}
|
tu se dalje moze svasta raditi. svatis elemente skupova kao proste brojeve, pa ti je zapravo skup isto sto i neki slozeni broj, te mu nadjes sve djelitelje...
_________________  |
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: 
Lokacija: /sbin/init
|
| Postano: 3:54 ned, 2. 1. 2005 Naslov: |
|
|
|
Ja sam vec odgovorio na topic i onda sam skuzio da sam odgovorio o ispisu svih podskupova, a ne svih particija, pa sam odustao od postanja... :(
Ahri, cini mi se da si i ti rijesio podskupove, a ne particije... :?
Ja sam vec odgovorio na topic i onda sam skuzio da sam odgovorio o ispisu svih podskupova, a ne svih particija, pa sam odustao od postanja... 
Ahri, cini mi se da si i ti rijesio podskupove, a ne particije... 
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
Gost
|
| Postano: 5:22 ned, 2. 1. 2005 Naslov: |
|
|
|
Ne, pa dobro je ljudi. Kako trebam particionirat na samo dvije particije, svako particioniranje je jednoznacno odredjeno prvom particijom, a druga se onda dobije komplementiranjem - dakle trazimo sve podskupove kardinaliteta <=n/2 (jer nije bitan poredak samih particija). Dakle ahri je u principu rijesio problem, jedino kaj u rekurziju treba stavit jos jedan argument - kolko smo do tog trenutka nafilali elemenata - da ne prijedjemo onda tih famoznih n/2.
Thanx ahri na ovakvom pogledu na multiskupove, to mi puno olaksava stvari. :D
Svima sve najbolje u novoj nam 2005-oj!
Ne, pa dobro je ljudi. Kako trebam particionirat na samo dvije particije, svako particioniranje je jednoznacno odredjeno prvom particijom, a druga se onda dobije komplementiranjem - dakle trazimo sve podskupove kardinaliteta <=n/2 (jer nije bitan poredak samih particija). Dakle ahri je u principu rijesio problem, jedino kaj u rekurziju treba stavit jos jedan argument - kolko smo do tog trenutka nafilali elemenata - da ne prijedjemo onda tih famoznih n/2.
Thanx ahri na ovakvom pogledu na multiskupove, to mi puno olaksava stvari. 
Svima sve najbolje u novoj nam 2005-oj!
|
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
| Postano: 5:32 ned, 2. 1. 2005 Naslov: |
|
|
|
tocno... tek sam sad malo bolje procitao
:(
ali slobodno ostavi, mozda ce nekom koristit. mozes editirat i nekom bojom napisati da je to rjesenje za podskupe
zapravo, vec osmislih nesto.
pod uvijetom da shvatimo multiskup kao neki prirodan broj (dakle, prosti brojevi na potencije) onda mozemo rijesiti slicno kao i zadatak "ispisi sve razlicite produkte koji daju broj N"
za npr. 24 to je
2*2*2*3
2*2*6
2*3*4
2*12
3*8
4*6
a taj zadatak sam rijesio ovako:
[code:1]
int rek(int n, int maxv) {
int sum=1;
for (int i=maxv; i*i<=n; i++)
if (n%i==0) sum+=rek(n/i, i);
return sum;
}
int refactor(int n) {
return rek(n, 2)-1;
}
[/code:1]
koji doduse ispisuje koliko ih ukupno ima, ali to se lahko preradi da ispise sto je dobio... te djelitelje (ili faktore) potrpamo u niz, i onda iz njih lako generiramo koji su to elementi multiskupa.
a ispisujemo npr. kada je n>maxv.
u mom zadatku je maxv je djelitelj, a n broj koji dijelim
i idem tako da stalno dijelim s brojevima koji su veci od prethodnih
npr. nakon sto 24 podijelim s 2, onda mogu nastavit dijelit s svim vecim od 2 .. ali ako ga u nekom trenu podijelim s 6, onda vise ne mogu s manjima od 6...
nadam se da me razumijete, ako ne, prosecite malo "rucno" kroz kod.
[10 mins later]
zapravo... evo, iskodirah.
ispise ti sve, a pretvaranje prostih brojeva u skupove ces zbilja sam... :). [napravi si listu prostih brojeva, strpaj to u niz i vrtiii:)]
[code:1]
#include <stdio.h>
#include <string.h>
int polje[50];
int k=0;
int ispisi() {
int i;
for(i=0;i<k;i++)
printf("%d ", polje[i]);
printf("\n");
return 0;
}
int rek(int n, int maxv) {
int sum=1;
if (n>maxv) {
polje[k]=n;
k++;
ispisi();
k--;
}
for (int i=maxv; i*i<=n; i++)
if (n%i==0) {
polje[k]=i; k++;
sum+=rek(n/i, i);
k--;
}
return sum;
}
int main() {
int n=24;
memset(polje, 0, sizeof(polje));
rek(n, 2)-1;
return 0;
}
[/code:1]
tocno... tek sam sad malo bolje procitao
:(
ali slobodno ostavi, mozda ce nekom koristit. mozes editirat i nekom bojom napisati da je to rjesenje za podskupe
zapravo, vec osmislih nesto.
pod uvijetom da shvatimo multiskup kao neki prirodan broj (dakle, prosti brojevi na potencije) onda mozemo rijesiti slicno kao i zadatak "ispisi sve razlicite produkte koji daju broj N"
za npr. 24 to je
2*2*2*3
2*2*6
2*3*4
2*12
3*8
4*6
a taj zadatak sam rijesio ovako:
| Kod: |
int rek(int n, int maxv) {
int sum=1;
for (int i=maxv; i*i<=n; i++)
if (n%i==0) sum+=rek(n/i, i);
return sum;
}
int refactor(int n) {
return rek(n, 2)-1;
}
|
koji doduse ispisuje koliko ih ukupno ima, ali to se lahko preradi da ispise sto je dobio... te djelitelje (ili faktore) potrpamo u niz, i onda iz njih lako generiramo koji su to elementi multiskupa.
a ispisujemo npr. kada je n>maxv.
u mom zadatku je maxv je djelitelj, a n broj koji dijelim
i idem tako da stalno dijelim s brojevima koji su veci od prethodnih
npr. nakon sto 24 podijelim s 2, onda mogu nastavit dijelit s svim vecim od 2 .. ali ako ga u nekom trenu podijelim s 6, onda vise ne mogu s manjima od 6...
nadam se da me razumijete, ako ne, prosecite malo "rucno" kroz kod.
[10 mins later]
zapravo... evo, iskodirah.
ispise ti sve, a pretvaranje prostih brojeva u skupove ces zbilja sam... :). [napravi si listu prostih brojeva, strpaj to u niz i vrtiii:)]
| Kod: |
#include <stdio.h>
#include <string.h>
int polje[50];
int k=0;
int ispisi() {
int i;
for(i=0;i<k;i++)
printf("%d ", polje[i]);
printf("\n");
return 0;
}
int rek(int n, int maxv) {
int sum=1;
if (n>maxv) {
polje[k]=n;
k++;
ispisi();
k--;
}
for (int i=maxv; i*i<=n; i++)
if (n%i==0) {
polje[k]=i; k++;
sum+=rek(n/i, i);
k--;
}
return sum;
}
int main() {
int n=24;
memset(polje, 0, sizeof(polje));
rek(n, 2)-1;
return 0;
}
|
_________________ |
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
|
| [Vrh] |
|
@#
Forumaš(ica)
Pridružen/a: 28. 01. 2004. (19:08:55)
Postovi: (36)16
Lokacija: math
|
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
|
| [Vrh] |
|
|
