Kombinacije(?) sa ponavljanjem
Imam niz od n elemenata. I treba da dobijem sve kombinacije (mozda nije pravo ime) sa odredjenim brojem ponavljanja elemenata. Gde svaki element moze da se pojavi od 0 do max broja ponavljanja. Redosled je bitan.
Npr: n=1,2,3 Broj ponavljanja: 2 Treba da dobijem: 1 1,1 1,2 1,3 1,1,1 1,2,1 1,2,2 1,2,3 1,3,1 1,3,2 1,3,3 1,1,2 1,1,3 1,1,2,2 1,1,3,3 1,1,2,3 1,2,1,3 1,2,3,1 1,2,2,1 1,2,1,2 ... 1,1,2,2,3,3 ... 3,3,1,1,2,2 3,3,1,2,2,1 ... Jel ima neko ideju kako ovo da resim u bilo kom programskom jeziku ? |
Nisam siguran kapiram li što hoćeš ;) ali ovo mi djeluje kao slučaj za nekoliko ugnježdenih for petlji.
[edit]Uteče mi quick reply prije nego sam završio, uskoro ću još dopisati[/edit] |
rekurzijom..
(svaki poziv funkcije odradi petlju za jednu poziciju, i unutar nje gleda da li treba da ide dalje u rekurziju ili je ispunjen uslov da je to ta kombinacija, u kom slucaju se vrati jedan stepen nazad) |
Mislio sam da li postoji neki algoritam za ovakve situacije ? Ili matematicka formula (iz koje bi dalje izveo algoritam) ?
|
mislim da je najpriblizniji algoritam obilazak stabla, ali specifican je problem, sumnjam da ces naci negde po koracima tacno uradi to i to...
EDIT: I kako moze da se pojavi 1,1,1 ako je max. broj pojavljivanja 2? |
Nedavno je neko trazio algoritam za skup podskupova - partitivni skup (power set), pretrazi forum.
Ono sto ti treba da uradis je da krenes od skupa u kome se ponavljaju elementi, (prakticno od multiskupa, u tvom primeru bi to bilo {1,1,2,2,3,3}, a ovo se lako generise) i tada dobijas {1} {2} {3} {1,1} {1,2} {1,3} {2,2} {2,3} {3,3} ... Kad ovako dobijes partitivni skup, jedino mislim da bi morao da uvedes malu modifikaciju - proveru da li vec postoji, da ne bi doslo do ponavljanja, i onda treba svaki element da "razvijes", tj. nadjes sve permutacije ovih elemenata, ali za to vec lako mozes da nadjes algoritam. |
Nisam te isprva dobro shvatio, pa sam smislio još jedno rješenje i ukapirao da ti ni to ne rješava sve probleme... :1054:
Možda ti ovo pomogne: Matematika - kombinacije i permutacije: http://mathforum.org/dr.math/faq/faq.comb.perm.html Algoritam za permutacije: http://www.merriampark.com/perm.htm Algoritam za kombinacije: http://www.merriampark.com/comb.htm Inače, krenuo sam bio ovim putem: Ako je n članova a k ponavljanja, prvo odrediti sve kombinacije (ili permutacije) k od n članova, a potom te dobijene skupove tretirati kao posebne promjenljive (nizove) i igrati se s njihovim kombinovanjem/permutovanjem. Možda i meni ujutru bude jasnije što sam htio reć. :) Uglavnom, permutacije tvog primjera {1,2,3} bile bi {1,2} {1,3} {2,1} {2,3} {3,1} {3,2} a kombinacije {1,2} {1,3} {2,3} E sad bi se trebalo nekako ponovo poigrati s njima da bi dobio to što ti treba. :) EDIT: Ili da isto poslušaš ovo što ti Japan kaže... Saslušaj nas i radi kako znaš :D |
Ah trebao sam vise da pratim na casovima matematike :) Videcu sta mogu da uradim ujutru ... hvala svima!
|
sad mi pade jos jedno resenje na pamet, nije efikasno, ali mi zvuci extra jednostavno za implementaciju:
dodas jos jedan element u skup: null, to jest element koji ne postoji, i koji kod ispisa ignorises. Onda samo uradis sve permutacije (jer je bitan redosled, kod kombinacija nije) elemenata skupa M na N mesta, pri cemu pamtis samo one rezultate koji zadovoljavaju tvoje kriterijume i nisu duplikati (svaka varijacija gde se desno od null nalazi broj koji nije null je automatski duplikat pa to preskaces) za permutacije imas primera koda koliko volis da nadjes... |
Kôd:
def var_p(niz, br_pon) Kôd:
>> var_p [1,2,3], 2 |
1,1,1 ne treba da ima, moja greska ... testiracu kasnije ;)
|
@jablan jel mozes da pojasnis malo kod kako bih ga preveo u php ili python. Tnx!
Citat:
|
Citat:
Kôd:
def var_p(niz, br_pon) |
^ Hvala :) Ja sam uspeo da napravim nesto u PHP-u ali moracu da nadjem drugi pristup jer mi memorija puca ...
|
O kolikim se nizovima i brojevima ponavljanja radi?
|
Trebalo bi da je ovo skoro direktan prevod u Python:
Kôd:
def my_perms(niz, br_pon): |
Hvala testiracu kasnije ;)
Niz se sastoji od 30ak elemenata (karaktera) a broj ponavljanja ide i do tri puta po karakteru. Nasao sam resenje, za sada, da pravim parcijalno samo delove koji mi ispunjavaju odredjene uslove. |
Oops.
Ne znam koliko poznaješ kombinatoriku (a trebalo bi barem malo, s obizirom da se baviš sigurnošću, što uključuje i određenu dozu kriptografije, koja je bukvalno zasnovana na kombinatorici): Niz od 30 elemenata ima 30! 30-permutacija (permutacija dužine 30). 30! = 265252859812191058636308480000000 Teško da iko poseduje disk na koji bi ta količina podataka mogla da se smesti. A da ne govorim šta bi se desilo da uključimo i 2-3 ponavljanja, gde bismo dobili 60! ili 90!. Jedino možeš da ograničiš broj elemenata u konačnom nizu, tako da ih imaš recimo maksimalno 3-4. Tek onda dobijaš neke razumne cifre. BTW, kako koristiš te permutacije posle? |
zapravo ima i vise, jer faktorijel je za permutacije bez ponavljanja, a ovde imas do 3 ponavljanja
|
Trebaju mi samo odredjene kombinacije ne sve, dodao sam par uslova i sada dobijam trazeni rezultat. Fajl ima ~80MB.
Hvala svima ;) p.s. Moracu da odvojim malo vise vremena za Ruby :) |
Vreme je GMT +2. Trenutno vreme je 06:05. |
Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.