|
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.
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.
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.
|
Posto mi se cini da te zanima programerski aspekt problema, ovaj topic cu zakljucati, a 
