Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

algoritam za izracunavanje svih mogucih kombinacija

[es] :: Art of Programming :: algoritam za izracunavanje svih mogucih kombinacija

[ Pregleda: 21898 | Odgovora: 15 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

sjanos
Subotica

Član broj: 28520
Poruke: 53
*.subotica.net

ICQ: 276006551


Profil

icon algoritam za izracunavanje svih mogucih kombinacija04.08.2004. u 14:03 - pre 239 meseci
Trebao bi mi algoritam za izracunavanje svih mogucih kombinacija za loto ako se iz M brojeva izvlaci N broj. (npr; M=90, N=12 znaci izvlacimo 12 brojeva iz 90, ovo je maksimalni broj sa kojim bih radio ukupan broj ovih kombinacija je 273897571557780) . radi se o loto kombinacijama znaci 1,5,7,9 je isto kao i 5,1,9,7. Vec danima trazim na internetu ali nista korisno ne mogu naci. Ja sam uradio nesto sa for ciklusima i if naredbom ali to samo radi sa unapred definisanim brojem parametra evo primera: (kod je u php-u zato sto sad u tome radim i to je bilo pri ruci ali sam program planiram da napisem ili u Visual C++ ili u Visual Basic (Visual Basic mi je mnogo blizi jer sam vec radio u njemu. koji mi preporucujete))
Code:
 $x=1;             //broji kombinacije
for ($i=1; $i<5; $i++)
{    
    for ($j=2; $j<6; $j++)
    {
        for ($z=3; $z<7; $z++)
        {
            for ($y=4; $y<7; $y++)
            {
                if ($i<$j && $j<$z && $z<$y)
                {
                    echo "$x: $i,$j,$z,$y<br>";
                    $x++;
                }
            }
        }
    }
}

ovde se racuna 4 brojeva iz 6 a rezultat je:
1: 1,2,3,4 2: 1,2,3,5 3: 1,2,3,6 4: 1,2,4,5 5: 1,2,4,6 6: 1,2,5,6 7: 1,3,4,5 8: 1,3,4,6 9: 1,3,5,6 10: 1,4,5,6 11: 2,3,4,5 12: 2,3,4,6 13: 2,3,5,6 14: 2,4,5,6 15: 3,4,5,6

Ove kombinacije bi mi trebale za dalju obradu, trebalo bi ih staviti u neki niz ili matricu ne znam koje je bolje resenje (u ovom primeru to ne radi). Uglavnom to je to. Mozda sam malo zbunjeno opisao problem ako ne bude jasno probacu malo lepse i jasnije da ga opisem :-)
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.et.tudelft.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija04.08.2004. u 14:10 - pre 239 meseci
Koliko juče poslah nešto o tome. Konkretno, algoritam za generisanje svih kombinacija.

f
 
Odgovor na temu

sjanos
Subotica

Član broj: 28520
Poruke: 53
*.subotica.net

ICQ: 276006551


Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija05.08.2004. u 09:07 - pre 239 meseci
mozda je u meni problem ali ja u ovom ne mogu da nadem nista korisno. sve neke matematicke formule koje bas i ne pomazu da napisem algoritam za PROGRAM.
Mozda neke druge sugestije??
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.decis.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija05.08.2004. u 09:17 - pre 239 meseci
Citat:
sjanos: mozda je u meni problem ali ja u ovom ne mogu da nadem nista korisno.


Nisi dobro ili nisi dovoljno čitao. Imaš datih nekoliko algoritama za generisanje kombinacija.

Niko nije rekao da je generisanje kombinacija nešto što može da se odradi u tri linije koda. Objašnjenje je dugačko a algoritam složen, šta da se radi.

f
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
217.119.242.*



+62 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija05.08.2004. u 10:19 - pre 239 meseci
Davno je to bilo, ali imao sam resenje tvog problema (kao amater sam dosta ucio pisuci program za loto).
Dakle, resenje je poziv funkcije kojoj prosledis brojeve n i m (n - ukupan broj elemenata; m - klasa kombinacija). U toj funkciji se inicijalizuje 'proto-kombinacija' koja u startu ima 0 brojeva (duzina nula).
Zatim, opet u toj funkciji pozivas drugu, REKURZIVNU sub-funkciju koja se sastoji od samo JEDNE for petlje. Sub-funkcija poziva samu sebe, razume se, i u svakom prolazu dodaje po jedan broj proto-kombinaciji; kad ispuni uslov (kompletira proto-kombinaciju m-te klase), zapise je u externi array (globalna varijabla), pa se zatim 'vraca' (back-tracking) i tako do kraja. Izgleda jednostavno, zar ne? Ali nije.

Kako sam dosao do ove zamisli? Prosto, u vreme kad sam to pisao imao sam pravu zver - Spectrum (Amstrad) + HISOFT Pascal. Generisanje punog sistema i provera svake kombinacije na uslove nije dolazila u obzir, pa sam radio optimizacije. Kako? Verovali ili ne, kombinacija moze da se odbaci (u zavisnosti od uslova) cak i kad imate samo 3, 4 ili 5 brojeva iste (umesto svih 7). Stos je u tome sto kad odbacite proto-kombinaciju od 4-5 brojeva, odbacili ste citavu genericku 'granu' koja NIKAKO ne moze zadovoljiti trazeni uslov. Razume se, nisu svi uslovi pogodni za ovako nesto.
Sistem od 600-700 kombinacija sa nekih 9-10 'teskih' uslova se generisao 3-4 sata. To su bila lepa vremena...
Pozdrav

Rajko
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija05.08.2004. u 10:41 - pre 239 meseci
Evo ovo sam pisao u 2. razredu srednje skole tako da nemoj mnogo da obracas paznju na stil (kod je skroz nemodularan uz koriscenje globalnih promenjivih):
Code:

#include <stdio.h>
int n,j,m,b[1000];
void stampajkomb(int k,int poz,int l)
{ int i;
  if (!k) {printf("\n%d: ",j++);for(i=0;i<l;i++)printf("%d ",b[i]);}
  else for(i=poz;i<=n-k+1;i++){b[l]=i;stampajkomb(k-1,i+1,l+1);}
}
int main()
{
  printf("\nUnesi broj elemenata\n");
  scanf("%d",&n);
  printf("\nKoliko elemenata biras od unetog broja elemenata?\n");
  scanf("%d",&m);
  j=1;
  stampajkomb(m,1,0);
  return 0;
}


U ovom kodu sam koristio Rajkovu ideju (u stvari to je bila moja ideja ali je ista kao ona gore).

[Ovu poruku je menjao srki dana 06.08.2004. u 17:55 GMT]
 
Odgovor na temu

stameni
Ivan Stamenković

Član broj: 6739
Poruke: 538



+9 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija05.08.2004. u 20:01 - pre 239 meseci
Pre izvesnog vremena u jednom od foruma neko je postovao izvanredan trik koji može pomoći i prilikom kombinacija bez ponavljanja. Na žalost, ne sećam se ko je postovao ideju, ali je mnogo dobra, i valjda se odnosila na varijacije. No, ovde imamo kombinacije. Pokušaću da opišem ideju u ovom slučaju.

Elem, neka je broj elemenata n, a klasa k. Formira se n-tocifreni binarni broj, koji je u početnom trenutku nula. Svakom njegovom bitu odgovara po jedna »kuglica iz bubnja«, pa ako je npr. peti bit jednak jedinici, izvučena je šestica.

Broj u petlji inkrementiramo. Kada broj jedinica tog broja u nekom trenutku postane jednak broju k, odštampamo indekse onih bitova koji su jednaki jedinici (eventualno uvećano za jedan). Iz petlje se izlazi kada svi bitovi postanu jednaki jedinici.

Definitivno iterativan algoritam sa svim prednostima i manama koje kao takav ima.
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
..-chandran.sbs.auckland.ac.nz



+3 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija05.08.2004. u 23:09 - pre 239 meseci
Taj algoritam je mnogo spor. A i za vise od 32 kuglice bi morao da pamtis broj kao niz i da pravis funkcije za dodavanje jedinice u taj broj-niz.
A takodje kada treba da izaberes recimo 2 broja od 100 onaj gore algoritam ti da resenje trenutno a tvoj algoritam ne bi zavrsio ni za 100 godina.
 
Odgovor na temu

sjanos
Subotica

Član broj: 28520
Poruke: 53
*.subotica.net

ICQ: 276006551


Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija07.08.2004. u 07:14 - pre 239 meseci
problem je u tome sto meni maximum broj kombinacija je 273897571557780 kako i u cemu to cuvati??? ne verujem da mogu napraviti(deklarisati) niz ove velicine.
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija07.08.2004. u 09:10 - pre 239 meseci
Nikome pri zdravoj pameti neće da trebaju u isto vreme sve te kombinacije, makar s njima igrao i loto. To što ti treba mora da se reši na drugi način.

f
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija07.08.2004. u 09:23 - pre 239 meseci
Citat:
sjanos: problem je u tome sto meni maximum broj kombinacija je 273897571557780 kako i u cemu to cuvati??? ne verujem da mogu napraviti(deklarisati) niz ove velicine.

Pa ne treba ti niz te velicine! Niz treba da ti bude veliki samo onoliko koliko ima elemenata u kombinaciji. Mada u svakom slucaju kao sto je Filip rekao, sigurno ti ne trebaju sve te kombinacije jer ne bi stigao da ih procitas ni da zivis 1000 godina. Ako kazes sta ti tacno treba verujem da neko moze da ti pomogne.

Poz.
 
Odgovor na temu

sjanos
Subotica

Član broj: 28520
Poruke: 53
*.subotica.net

ICQ: 276006551


Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija07.08.2004. u 12:21 - pre 239 meseci
ne treba mi da procitam, nego da posle ove kombinacije pustim kroz odreden broj filtera. unapred se ne zna broj filtera nego ce se oni usput dodavati. moze da se desi da neki filter izbaci samo mali broj kombinacija. u svakom slucaju nece se prikazivati ovoliki broj kombinacija to ne koristi nicemu. po mom misljenju maximalni broj prikazanih kombinacija bice negde oko 1000-2000 ne verujem da ce nekome biti potrebno vise od toga. inace pravim klon jednog loto programa ako nekome to pomaze mogu mu poslati demo verziju istog posto samo to imam.
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
217.119.242.*



+62 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija07.08.2004. u 14:30 - pre 239 meseci
Nisi pazljivo procitao moj post o prastarom loto programu.
Code:

Zatim, opet u toj funkciji pozivas drugu, REKURZIVNU sub-funkciju koja se sastoji od samo JEDNE for petlje. Sub-funkcija poziva samu sebe, razume se, i u svakom prolazu dodaje po jedan broj proto-kombinaciji; kad ispuni uslov (kompletira proto-kombinaciju m-te klase), zapise je u externi array (globalna varijabla), pa se zatim 'vraca' (back-tracking) i tako do kraja. Izgleda jednostavno, zar ne? Ali nije.


Obrati paznju na ono 'kad ispuni uslov...'. Gore navedeni uslov je duzina proto-kombinacije; a ko ti brani da TADA proto-kombinaciju propustis kroz tvoje filtere, pa tek ako prodje da je memorises u niz?

Rajko
 
Odgovor na temu

sjanos
Subotica

Član broj: 28520
Poruke: 53
*.subotica.net

ICQ: 276006551


Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija09.08.2004. u 08:40 - pre 239 meseci
na to sam i ja mislio. probacu tako da uradim da prvo samo prikaze broj kombinacija koje su ostale posle filtera a kad dode do nekog razumnog broja onda ce omoguciti prikaz tih kombinacija. inace koja je maksimalna velicina niza? da li zavisi od programskog jezika? da li je preporucljivo ovakav program raditi u visual basic-u?
inace hvala vam na pomoci.
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
217.119.242.*



+62 Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija09.08.2004. u 09:24 - pre 239 meseci
Na danasnjim masinama velicina niza je ogranicena velicinom virtuelnog RAM-a...

Rajko

P.S. Dobro, broj kombinacija je ogranicen rasponom integer-a, a to je 2^31 (kako gde).
 
Odgovor na temu

blaza1995
anamarija blažević
studentica
zadar

Član broj: 332955
Poruke: 1
*.cust.tele2.hr.



Profil

icon Re: algoritam za izracunavanje svih mogucih kombinacija21.03.2016. u 02:14 - pre 97 meseci
moze li mi netko izračunati sve moguće kombinacije na recimo 4 para (kladionica) recimo zbroj golova više ili manje ako je moguć ishod 1 ili ishos 2 znam da ih ima 16 ali ako netko može ispisati niz,nova sam na forumu stoga isprike ako sam nešto krivo napisala,molim pomoć dečki hvala =) =) =)
 
Odgovor na temu

[es] :: Art of Programming :: algoritam za izracunavanje svih mogucih kombinacija

[ Pregleda: 21898 | Odgovora: 15 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.