☰

» »

Algoritem za zapis kombinacij

Algoritem za zapis kombinacij

energetik ::

Torej iščem algoritem, kjer bi zapisal vse možne kombinacije določenih števil:
Recimo da imam števila p1, p2,..., pn
Želim pa dobiti ven vse kombinacije: p1, p2,...,pn, p1+p2,...,p1+pn, p1+p2+pn,...p1+p2+...+pn

Kakšen bi bil najenostavnejši algoritem? Tuhtam že 2 dni, pa mi nič razen n-krat for zanka ne pade v glavo.
Nekako bi bilo treba vedno prištevat osnovna števila p1, p2,..., pn k že izračunanim vsotam.
Vem, da je kombinacij 2^n-1, ampak kako vse to zapisat...

DavidJ ::

Ne razumem te povsem. Napisi na primeru stevilk 1, 2 in 3.

Permutacije: 123, 132, 213, 231, 312, 321.
Sestevki: 1+2, 1+3, 2+1, 2+3, 3+1, 3+2, 1+2+3.

Sem kaj pozabil?
"Do, or do not. There is no 'try'. "
- Yoda ('The Empire Strikes Back')

joze67 ::

Simpl. Zanka od 1 do 2^n-1, števec pretvoriš v dvojiški sistem, potem vzameš člene na mestih, kjer je 1

energetik ::

DavidJ je izjavil:

Ne razumem te povsem. Napisi na primeru stevilk 1, 2 in 3.

Permutacije: 123, 132, 213, 231, 312, 321.
Sestevki: 1+2, 1+3, 2+1, 2+3, 3+1, 3+2, 1+2+3.

Sem kaj pozabil?

Ja imaš recimo številke: 5, 8, 3
Hočem dobiti 5,8,3,5+8,5+3,8+3,5+8+3 za N takih številk.

Joze67, zanimiva ideja. Približn kapiram, kako misliš. Bom poskusil...
Torej če mam 3 cifre:
1___001
2___010
3___011
4___100
5___101
6___110
7___111
In potem samo seštevam cifre na mestih kjer je enica? Zgleda OK.

Zgodovina sprememb…

  • spremenilo: energetik ()

energetik ::

Joze67, hvala za tole idejo, deluje. Problem je samo to, da Excelova funkcija DEC2BIN pretvarja samo cifre do 2^9, torej do 512 kombinacij. Jaz bi pa rabil recimo do ~2^25 kombinacij, da izkoristim celo delovno površino v Excelu...
Kako bi se dalo sprogramirati pretovorbo v binarno obliko za tako velike cifre? Kakšna ideja?

prtenjam ::

Na strani Matjazev.NET imaš Excelov dodatek mDodatki. v Slednjem se nahaja funkcija mDec2bin, ki zna pretvarjati do števil 2^31 (kolikor je omejitev realnih števil v Excelu).
Matjaž Prtenjak
https://mnet.si

energetik ::

Aha, hvala. Sem že uporabil Matlab, ki ima DEC2BIN do 2^52...
Računal mi je pa za 2^20 kombinacij ~15h...nisem si mislil, da na današnjih kištah to poteka tolk počasi (1 obremenjeno jedro C2D @2,66GHz).

Steinkauz ::

2^20 kombinacij, to ne more hitro zračunati.
Na starih kištah bi rabu par dni :))

alexa-lol ::

o shit... ti isces potencno množico brez prazne množice
http://www.mathisfunforum.com/viewtopic...

oz. isci za power set algorithm

DavidJ ::

Vau, kero kompliciranje. Tako kot ti je povedal alexa-lol, iščeš vse podmnožice množice mnižice z N elementi, razen prazne. Torej vse možne kombinacije med N elementi, brez prazne. Algoritem, ki sta ga Sedgewick in Wayne spisala samo zate.
"Do, or do not. There is no 'try'. "
- Yoda ('The Empire Strikes Back')

energetik ::

DavidJ, sej sm napisal, da sem že naredil. Ne rabiš nobenega algoritma, samo pretvoriš cifre od 0 do 2^n v binarno obliko in imaš kombinacije zapisane z enicami.

WarpedGone ::

Računal mi je pa za 2^20 kombinacij ~15h...nisem si mislil, da na današnjih kištah to poteka tolk počasi (1 obremenjeno jedro C2D @2,66GHz).

Tvoj program ponuca 150.000 operacij/ciklov da obdela eno kombinacijo. Mogoče je problem v programerju, ne računalniku?
Zbogom in hvala za vse ribe

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Kombinatorika

Oddelek: Šola		191992 (1333) 2f4u
»

pomoč matematika - kombinatorika!

Oddelek: Šola		101279 (943) technolog
»

Stevilo kvadratov vzorca

Oddelek: Šola		172326 (1960) lebdim
»

[c++] naloge

Oddelek: Programiranje		476141 (4681) technolog
»

Pomoč: kako naštudirati domine

Oddelek: Šola		71421 (1018) marko29

Več podobnih tem