Kombinacije(?) sa ponavljanjem

Ivan · 20. 06. 2010.

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.

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.

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.

Mislio sam da li postoji neki algoritam za ovakve situacije ? Ili matematicka formula (iz koje bi dalje izveo algoritam) ?

ivanhoe · 21. 06. 2010.

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.

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.

Nisam te isprva dobro shvatio, pa sam smislio još jedno rješenje i ukapirao da ti ni to ne rješava sve probleme...

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š

Ivan · 21. 06. 2010.

Ah trebao sam vise da pratim na casovima matematike

Videcu sta mogu da uradim ujutru ... hvala svima!

ivanhoe · 21. 06. 2010.

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.

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.

20. 06. 2010.	#1
Ivan Psychedelictrance freak Wrote a book Datum učlanjenja: 04.06.2006 Lokacija: Srbija, Beograd Poruke: 1.008 Hvala: 325 933 "Hvala" u 34 poruka	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 ? __________________ Testiranje bezbednosti web aplikacija

20. 06. 2010.	#2
Milos Vukotic Knowledge base Wrote a book Datum učlanjenja: 07.06.2005 Lokacija: Neđe ođe... Poruke: 1.198 Hvala: 339 688 "Hvala" u 178 poruka	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] __________________ Чак Норис може да си ги врзе врвките на чевлите со стапалата.

20. 06. 2010.	#3
ivanhoe Ivan Dilber Sir Write-a-Lot Datum učlanjenja: 18.10.2005 Lokacija: Bgd Poruke: 5.320 Hvala: 104 2.344 "Hvala" u 583 poruka	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) __________________ Leadership is the art of getting people to want to do what you know must be done. Poslednja izmena od ivanhoe : 21. 06. 2010. u 00:00.

20. 06. 2010.	#4
Ivan Psychedelictrance freak Wrote a book Datum učlanjenja: 04.06.2006 Lokacija: Srbija, Beograd Poruke: 1.008 Hvala: 325 933 "Hvala" u 34 poruka	Mislio sam da li postoji neki algoritam za ovakve situacije ? Ili matematicka formula (iz koje bi dalje izveo algoritam) ? __________________ Testiranje bezbednosti web aplikacija

21. 06. 2010.	#5
ivanhoe Ivan Dilber Sir Write-a-Lot Datum učlanjenja: 18.10.2005 Lokacija: Bgd Poruke: 5.320 Hvala: 104 2.344 "Hvala" u 583 poruka	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? __________________ Leadership is the art of getting people to want to do what you know must be done. Poslednja izmena od ivanhoe : 21. 06. 2010. u 00:10.

21. 06. 2010.	#6
japan novi klan Professional Datum učlanjenja: 03.02.2007 Poruke: 326 Hvala: 43 427 "Hvala" u 50 poruka	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. __________________ We professional we dealin' with business Poslednja izmena od japan : 21. 06. 2010. u 01:15.