DevProTalk
Strana 1 od 2 1 2 >
Prikažite 40 poruka iz ove teme na jednoj stani

DevProTalk (http://www.devprotalk.com/index.php)
-   Programiranje (http://www.devprotalk.com/forumdisplay.php?f=23)
-   -   Kombinacije(?) sa ponavljanjem (http://www.devprotalk.com/showthread.php?t=8852)

Ivan 20. 06. 2010. 23:03
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 ?

Milos Vukotic 20. 06. 2010. 23:51
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]

ivanhoe 20. 06. 2010. 23:54
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)

Ivan 20. 06. 2010. 23:57
Mislio sam da li postoji neki algoritam za ovakve situacije ? Ili matematicka formula (iz koje bi dalje izveo algoritam) ?

ivanhoe 21. 06. 2010. 00:02
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?

japan 21. 06. 2010. 01:06
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.

Milos Vukotic 21. 06. 2010. 01:27
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

Ivan 21. 06. 2010. 02:08
Ah trebao sam vise da pratim na casovima matematike :) Videcu sta mogu da uradim ujutru ... hvala svima!

ivanhoe 21. 06. 2010. 02:55
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...

jablan 21. 06. 2010. 09:51
Kôd:
def var_p(niz, br_pon)
  niz = (niz*br_pon).sort
  (1..niz.length).inject([]){|a,i| a + niz.permutation(i).to_a}.uniq
end
daje

Kôd:
>> var_p [1,2,3], 2
=> [[1], [2], [3], [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3], [1, 1, 2], [1, 1, 3], [1, 2, 1], [1, 2, 2], [1, 2, 3], [1, 3, 1], [1, 3, 2], [1, 3, 3], [2, 1, 1], [2, 1, 2], [2, 1, 3], [2, 2, 1], [2, 2, 3], [2, 3, 1], [2, 3, 2], [2, 3, 3], [3, 1, 1], [3, 1, 2], [3, 1, 3], [3, 2, 1], [3, 2, 2], [3, 2, 3], [3, 3, 1], [3, 3, 2], [1, 1, 2, 2], [1, 1, 2, 3], [1, 1, 3, 2], [1, 1, 3, 3], [1, 2, 1, 2], [1, 2, 1, 3], [1, 2, 2, 1], [1, 2, 2, 3], [1, 2, 3, 1], [1, 2, 3, 2], [1, 2, 3, 3], [1, 3, 1, 2], [1, 3, 1, 3], [1, 3, 2, 1], [1, 3, 2, 2], [1, 3, 2, 3], [1, 3, 3, 1], [1, 3, 3, 2], [2, 1, 1, 2], [2, 1, 1, 3], [2, 1, 2, 1], [2, 1, 2, 3], [2, 1, 3, 1], [2, 1, 3, 2], [2, 1, 3, 3], [2, 2, 1, 1], [2, 2, 1, 3], [2, 2, 3, 1], [2, 2, 3, 3], [2, 3, 1, 1], [2, 3, 1, 2], [2, 3, 1, 3], [2, 3, 2, 1], [2, 3, 2, 3], [2, 3, 3, 1], [2, 3, 3, 2], [3, 1, 1, 2], [3, 1, 1, 3], [3, 1, 2, 1], [3, 1, 2, 2], [3, 1, 2, 3], [3, 1, 3, 1], [3, 1, 3, 2], [3, 2, 1, 1], [3, 2, 1, 2], [3, 2, 1, 3], [3, 2, 2, 1], [3, 2, 2, 3], [3, 2, 3, 1], [3, 2, 3, 2], [3, 3, 1, 1], [3, 3, 1, 2], [3, 3, 2, 1], [3, 3, 2, 2], [1, 1, 2, 2, 3], [1, 1, 2, 3, 2], [1, 1, 2, 3, 3], [1, 1, 3, 2, 2], [1, 1, 3, 2, 3], [1, 1, 3, 3, 2], [1, 2, 1, 2, 3], [1, 2, 1, 3, 2], [1, 2, 1, 3, 3], [1, 2, 2, 1, 3], [1, 2, 2, 3, 1], [1, 2, 2, 3, 3], [1, 2, 3, 1, 2], [1, 2, 3, 1, 3], [1, 2, 3, 2, 1], [1, 2, 3, 2, 3], [1, 2, 3, 3, 1], [1, 2, 3, 3, 2], [1, 3, 1, 2, 2], [1, 3, 1, 2, 3], [1, 3, 1, 3, 2], [1, 3, 2, 1, 2], [1, 3, 2, 1, 3], [1, 3, 2, 2, 1], [1, 3, 2, 2, 3], [1, 3, 2, 3, 1], [1, 3, 2, 3, 2], [1, 3, 3, 1, 2], [1, 3, 3, 2, 1], [1, 3, 3, 2, 2], [2, 1, 1, 2, 3], [2, 1, 1, 3, 2], [2, 1, 1, 3, 3], [2, 1, 2, 1, 3], [2, 1, 2, 3, 1], [2, 1, 2, 3, 3], [2, 1, 3, 1, 2], [2, 1, 3, 1, 3], [2, 1, 3, 2, 1], [2, 1, 3, 2, 3], [2, 1, 3, 3, 1], [2, 1, 3, 3, 2], [2, 2, 1, 1, 3], [2, 2, 1, 3, 1], [2, 2, 1, 3, 3], [2, 2, 3, 1, 1], [2, 2, 3, 1, 3], [2, 2, 3, 3, 1], [2, 3, 1, 1, 2], [2, 3, 1, 1, 3], [2, 3, 1, 2, 1], [2, 3, 1, 2, 3], [2, 3, 1, 3, 1], [2, 3, 1, 3, 2], [2, 3, 2, 1, 1], [2, 3, 2, 1, 3], [2, 3, 2, 3, 1], [2, 3, 3, 1, 1], [2, 3, 3, 1, 2], [2, 3, 3, 2, 1], [3, 1, 1, 2, 2], [3, 1, 1, 2, 3], [3, 1, 1, 3, 2], [3, 1, 2, 1, 2], [3, 1, 2, 1, 3], [3, 1, 2, 2, 1], [3, 1, 2, 2, 3], [3, 1, 2, 3, 1], [3, 1, 2, 3, 2], [3, 1, 3, 1, 2], [3, 1, 3, 2, 1], [3, 1, 3, 2, 2], [3, 2, 1, 1, 2], [3, 2, 1, 1, 3], [3, 2, 1, 2, 1], [3, 2, 1, 2, 3], [3, 2, 1, 3, 1], [3, 2, 1, 3, 2], [3, 2, 2, 1, 1], [3, 2, 2, 1, 3], [3, 2, 2, 3, 1], [3, 2, 3, 1, 1], [3, 2, 3, 1, 2], [3, 2, 3, 2, 1], [3, 3, 1, 1, 2], [3, 3, 1, 2, 1], [3, 3, 1, 2, 2], [3, 3, 2, 1, 1], [3, 3, 2, 1, 2], [3, 3, 2, 2, 1], [1, 1, 2, 2, 3, 3], [1, 1, 2, 3, 2, 3], [1, 1, 2, 3, 3, 2], [1, 1, 3, 2, 2, 3], [1, 1, 3, 2, 3, 2], [1, 1, 3, 3, 2, 2], [1, 2, 1, 2, 3, 3], [1, 2, 1, 3, 2, 3], [1, 2, 1, 3, 3, 2], [1, 2, 2, 1, 3, 3], [1, 2, 2, 3, 1, 3], [1, 2, 2, 3, 3, 1], [1, 2, 3, 1, 2, 3], [1, 2, 3, 1, 3, 2], [1, 2, 3, 2, 1, 3], [1, 2, 3, 2, 3, 1], [1, 2, 3, 3, 1, 2], [1, 2, 3, 3, 2, 1], [1, 3, 1, 2, 2, 3], [1, 3, 1, 2, 3, 2], [1, 3, 1, 3, 2, 2], [1, 3, 2, 1, 2, 3], [1, 3, 2, 1, 3, 2], [1, 3, 2, 2, 1, 3], [1, 3, 2, 2, 3, 1], [1, 3, 2, 3, 1, 2], [1, 3, 2, 3, 2, 1], [1, 3, 3, 1, 2, 2], [1, 3, 3, 2, 1, 2], [1, 3, 3, 2, 2, 1], [2, 1, 1, 2, 3, 3], [2, 1, 1, 3, 2, 3], [2, 1, 1, 3, 3, 2], [2, 1, 2, 1, 3, 3], [2, 1, 2, 3, 1, 3], [2, 1, 2, 3, 3, 1], [2, 1, 3, 1, 2, 3], [2, 1, 3, 1, 3, 2], [2, 1, 3, 2, 1, 3], [2, 1, 3, 2, 3, 1], [2, 1, 3, 3, 1, 2], [2, 1, 3, 3, 2, 1], [2, 2, 1, 1, 3, 3], [2, 2, 1, 3, 1, 3], [2, 2, 1, 3, 3, 1], [2, 2, 3, 1, 1, 3], [2, 2, 3, 1, 3, 1], [2, 2, 3, 3, 1, 1], [2, 3, 1, 1, 2, 3], [2, 3, 1, 1, 3, 2], [2, 3, 1, 2, 1, 3], [2, 3, 1, 2, 3, 1], [2, 3, 1, 3, 1, 2], [2, 3, 1, 3, 2, 1], [2, 3, 2, 1, 1, 3], [2, 3, 2, 1, 3, 1], [2, 3, 2, 3, 1, 1], [2, 3, 3, 1, 1, 2], [2, 3, 3, 1, 2, 1], [2, 3, 3, 2, 1, 1], [3, 1, 1, 2, 2, 3], [3, 1, 1, 2, 3, 2], [3, 1, 1, 3, 2, 2], [3, 1, 2, 1, 2, 3], [3, 1, 2, 1, 3, 2], [3, 1, 2, 2, 1, 3], [3, 1, 2, 2, 3, 1], [3, 1, 2, 3, 1, 2], [3, 1, 2, 3, 2, 1], [3, 1, 3, 1, 2, 2], [3, 1, 3, 2, 1, 2], [3, 1, 3, 2, 2, 1], [3, 2, 1, 1, 2, 3], [3, 2, 1, 1, 3, 2], [3, 2, 1, 2, 1, 3], [3, 2, 1, 2, 3, 1], [3, 2, 1, 3, 1, 2], [3, 2, 1, 3, 2, 1], [3, 2, 2, 1, 1, 3], [3, 2, 2, 1, 3, 1], [3, 2, 2, 3, 1, 1], [3, 2, 3, 1, 1, 2], [3, 2, 3, 1, 2, 1], [3, 2, 3, 2, 1, 1], [3, 3, 1, 1, 2, 2], [3, 3, 1, 2, 1, 2], [3, 3, 1, 2, 2, 1], [3, 3, 2, 1, 1, 2], [3, 3, 2, 1, 2, 1], [3, 3, 2, 2, 1, 1]]
Nisam samo siguran da li je to to što tebi treba, ko što reče ivanhoe, [1,1,1] ne bi trebalo da imaš, prema postavci, a opet ga imaš u svom primeru.


Vreme je GMT +2. Trenutno vreme je 01:52.
Strana 1 od 2 1 2 >
Prikažite 40 poruka iz ove teme na jednoj stani

Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.

Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.