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

Algoritam za broj kombinacija bez ponavljanja

[es] :: Art of Programming :: Algoritam za broj kombinacija bez ponavljanja

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

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

bluesman

Član broj: 4505
Poruke: 1895
*.26.EUnet.yu



+1 Profil

icon Algoritam za broj kombinacija bez ponavljanja12.08.2002. u 01:11 - pre 263 meseci
Da li moze neko da mi pomogne oko algoritma za broj kombinacija bez ponavljanja. Tacnije, broj kombinacija znam da izracunam, to je
Code:

k od n =
    n! 
-------------
(n-k)! * k!

ali meni treba algoritam za ispisivanje svih kombinacija!

Znaci, na primer imamo 2 od 4, broj kombinacija je 4!/2! * 2! = 4*3/2 = 6. Znaci ima 6 kombinacija bez ponavljanja. Meni treba algoritam koji ce da "raspise" sve kombinacije:

kombinacija 1: 0 1
kombinacija 2: 0 2
kombinacija 3: 0 3
kombinacija 4: 1 2
kombinacija 5: 1 3
kombinacija 6: 2 3

Sta ako imam 9 od 15?
Goran Pilipović fka bluesman
 
Odgovor na temu

bluesman

Član broj: 4505
Poruke: 1895
*.52.EUnet.yu



+1 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja12.08.2002. u 15:37 - pre 263 meseci
sta se desava? Niko nema cak ni ideju?

Ne ocekujem da mi se napise ceo algoritam, bar neka ideja.
Goran Pilipović fka bluesman
 
Odgovor na temu

Milos^
Beograd

Član broj: 4596
Poruke: 11
195.250.105.*



Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja13.08.2002. u 03:51 - pre 263 meseci
Citat:

kombinacija 1: 0 1
kombinacija 2: 0 2
kombinacija 3: 0 3
kombinacija 4: 1 2
kombinacija 5: 1 3
kombinacija 6: 2 3


Pocnes od prve kombinacije, npr. ako trazis 9 od 15, to ce biti
1 2 3 4 5 6 7 8 9,
sledecu nalazis ako povecas poslednji broj za 1, i to je
1 2 3 4 5 6 7 8 10.
Kad dodjes do kombinacije
1 2 3 4 5 6 7 8 15,
sledecu dobijas tako sto odes jos jedno mesto levo, i taj broj povecas za jedan, a na sledecu poziciju upises broj za jedan veci:
1 2 3 4 5 6 7 9 10.

Generalno, ako ti je poslednja cifra manja od 15, samo je povecas za 1 i dobio si sledecu kombinaciju. Ako je 15, ides levo, ako je broj na levoj pozicji 14, ides jos jedno mesto ulevo itd. dok se ne prekine taj niz. Broj do koga si stigao povecas za 1, i do kraja upisujes redom brojeve vece od tog. Na primer, ako imas kombinaciju
1 2 3 4 5 12 13 14 15,
sledeca je
1 2 3 4 6 7 8 9 10.


 
Odgovor na temu

Krsta
Krstić Dejan
Programer & Web Developer
Kruševac

Član broj: 2461
Poruke: 307
*.ptt.yu

Sajt: www.atec.rs


+15 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja13.08.2002. u 18:01 - pre 263 meseci
Imam Source code radjen u VB-u, posto sam i ja imao slican problem. Ako ti nesto znaci postovacu ovde.

Pozdrav.
 
Odgovor na temu

jc denton

Član broj: 2358
Poruke: 1705
*.ptt.yu



Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja13.08.2002. u 20:11 - pre 263 meseci
Krsto, ajde daj taj kod, i mene interesuje.

pozdrav
fire, walk with me
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.verat.net



+3 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja14.08.2002. u 00:35 - pre 263 meseci
Evo ovo sam radio pre nekih 8-9 godina kada sam ucio C pa sam sada iskopao :
Code:

#include <stdio.h>
#include <string.h>
int n;
char a[20];
char b[20];
void stampajkomb(int k,int d,int l)
{ int i;
  if (!k) {printf("\n");b[l]=0;printf("%s",b);}
  else for(i=d;i<=n-k;i++){b[l]=a[i];stampajkomb(k-1,i+1,l+1);}
}
main()
{
  int i;
  printf("\nUnesi elemente\n");
  scanf("%s",&a);
  n=strlen(&a);
  for(i=1;i<=n;i++)
  {  printf("\n");
     stampajkomb(i,0,0);
   }
}


Elementi su ti u stvari karakteri stringa. Npr. stavi da ti je string ABCDEF ili 123456 pa ce ti elementi biti slova ili cifre.

ako zelis recimo kombinacije 2 elementa od n onda umesto
for(i=1;i<=n;i++)
{ printf("\n");
stampajkomb(i,0,0);
}

stavi stampajkomb(2,0,0)
 
Odgovor na temu

Krsta
Krstić Dejan
Programer & Web Developer
Kruševac

Član broj: 2461
Poruke: 307
*.ptt.yu

Sajt: www.atec.rs


+15 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja14.08.2002. u 02:49 - pre 263 meseci
Citat:
jc denton:
Krsto, ajde daj taj kod, i mene interesuje.


Pa gde si ti Dentone, ajde ovo je tvoja oblast, ti si strucnjak za te stvari. Nemoj ja da odgovaram umesto tebe sa tvojim resenjem.

Poz...
 
Odgovor na temu

Milos^
Beograd

Član broj: 4596
Poruke: 11
195.250.105.*



Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja14.08.2002. u 04:32 - pre 263 meseci
Ova f-ja daje sledecu kombinaciju:
Code:

int sledeca (int komb[], int n, int k)
{
   int l=k-1,x;
   while (l>=0 && komb[l]==--n) l--;
   if (l<0) return 0;
   x=komb[l];
   do komb[l++]=++x; while (l<k);
   return 1;
}


Prakticna je ako sa kombinacijama treba raditi jos nesto sem ispisa, a ispis za npr. 9 od 15 bi isao ovako:

Code:

 int j;
   int komb[9];
   for (j=0; j<9; j++) komb[j]=j;
   do 
   { for (j=0; j<9; j++) printf("%d ", komb[j]); 
     printf("\n");
   }
   while(sledeca(komb, 15, 9));
 
Odgovor na temu

jc denton

Član broj: 2358
Poruke: 1705
*.ptt.yu



Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja14.08.2002. u 11:54 - pre 263 meseci
Citat:
Krsta:
Pa gde si ti Dentone, ajde ovo je tvoja oblast, ti si strucnjak za te stvari. Nemoj ja da odgovaram umesto tebe sa tvojim resenjem.


Resenje nije kompletno :), a mislim da smo ja i ti svojevremeno razgovarali o permutacijama ili gresim ? Na koji kod si mislio ?
fire, walk with me
 
Odgovor na temu

bluesman

Član broj: 4505
Poruke: 1895
*.254.EUnet.yu



+1 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja16.08.2002. u 18:25 - pre 263 meseci
Evo ja sam nesto radio i radi ok, mada u nekim slucajevima (recimo kada racuna 9 od 10) ne ispise dobro. Kod je naravno "iz prve ruke, na divljaka" pa nije ni optimizovan, pa ako neko ima vremena da pogleda gde je taj jebeni bug. Znaci, iz funkcije se vraca array of arrays.

Code:

function Raspisi ($trazeno, $pogodjeno)
{
$k = array();
$broj_kombinacija = BrojKombinacija ($trazeno, $pogodjeno);

for ($i=0; $i < $trazeno; $i++)                /* upisi prvu kombinaciju, sigurno znas koja je */
$k[1][$i] = $i;
$komb = 2; // kreni od 2. kombinacije

while ($komb <= $broj_kombinacija) {
    $temp = $k[$komb-1]; // uzmi prethodni niz
    $col = $trazeno-1;      // poslednji element u nizu
    $last_val = $temp[$col];
    if ($last_val < $pogodjeno-1)
    {
    $k[$komb] = $temp;     // prepisi celi kombinaciju    
    $val = array_pop ($temp);    // get the last element
    $k[$komb][$col] = $val + 1;    // zameni samo posledji, uvecan za 1
    }
else // nije manji, onda je najveci
    {
    $i = $col-1;
    while ($i >= 0)
    {
    if ($temp[$i]+1 < $temp[$i+1] && $temp[$i] <= $pogodjeno-$i-1)
        break;
    $i--;
    }
    if ($i >= 0)
    {
    $k[$komb] = $temp;    // prepisi celi kombinaciju
    $val = $temp[$i] + 1;
    for ($n = $i; $n < $trazeno; $n++)
        {
        if ($val < $pogodjeno)
        $k[$komb][$n] = $val++;
        }
    }
}
$komb++;
}

    return $k;
}

function fact ($n)
{
for ($r = 1; $n > 0; $n--)
    $r *= $n;
return $r;
}
    
function BrojKombinacija ($trazi, $od)
{
return fact ($od) / (fact ($od-$trazi) * fact($trazi));
}

Goran Pilipović fka bluesman
 
Odgovor na temu

mucky
Aleksandar Mastilović
Freelancer
Novi Sad - Srbija

Član broj: 237
Poruke: 412
*.telekom.yu



+1 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja21.08.2002. u 13:19 - pre 263 meseci
Evo ja sam ga uradio na nacin na koji kontam da treba. Ne mogu bas da provalim taj tvoj kod, vidim da si pravio dvodimenzionalni niz i u njega smestao resenja, ali ne razumem zbog cega? Trebalo bi manipulisati jednim jednodimenzionim nizom, i samo povecavati odredjene cifre... Evo ti kod pa pogledaj, bice mi drago ako ti bude koristio
Prikačeni fajlovi
 
Odgovor na temu

bluesman

Član broj: 4505
Poruke: 1895
*.195.EUnet.yu



+1 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja21.08.2002. u 15:25 - pre 263 meseci
Meni reba dvodimenzionalni niz zato sto mi treba za manipulaciju kasnije. Nije dovoljno samo da ispisem vec imam i izracunavanja. Znaci ja u taj niz smestam indekse elemenata.
Ako imam 3 od 5, znaci 10 kombinacija imam niz od 10 nizova sa indeksima elemenata koji ulaze u tu kombinaciju
k[0] = array (0, 1, 2)
k[2] = array (0, 1, 3)
... itd
i taj array se vraca iz funkcije pa sa njim mogu da radim sta hocu
Goran Pilipović fka bluesman
 
Odgovor na temu

mucky
Aleksandar Mastilović
Freelancer
Novi Sad - Srbija

Član broj: 237
Poruke: 412
*.telekom.yu



+1 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja21.08.2002. u 16:37 - pre 263 meseci
Aha, kontam. Ako taj tvoj algoritam ne radi dobro, onda ovaj sto sam ga postovao mozes prepraviti da umesto sto stampa na ekran jednostavno tura svako resenje u taj tvoj niz nizova, i eto resenja
 
Odgovor na temu

bluesman

Član broj: 4505
Poruke: 1895
*.82.EUnet.yu



+1 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja21.08.2002. u 16:50 - pre 263 meseci
Hvala ti,
ja sam u stvari hteo da provalim zasto mi recimo ispisuje sve kako treba ali za neku varijantu ispise pogresno. Recimo kada radim 4 od 15, 5 od 15, 6/15, ... 13/15 - uradi kako treba ali za 14/15 ne radi. Pri tom nema pravila.

Ali 'ajde da ne smaram, pregledacu tvoj kod pa da vidim.
Cheers
Goran Pilipović fka bluesman
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.verat.net



+3 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja21.08.2002. u 22:00 - pre 263 meseci
I moje resenje moze da prepravi da umesto stampanja samo smesta u niz.
Je l' si probao da startujes ono moje?
 
Odgovor na temu

bluesman

Član broj: 4505
Poruke: 1895
*.150.EUnet.yu



+1 Profil

icon Re: Algoritam za broj kombinacija bez ponavljanja23.08.2002. u 14:19 - pre 262 meseci
Citat:
mucky:
Aha, kontam. Ako taj tvoj algoritam ne radi dobro, onda ovaj sto sam ga postovao mozes prepraviti da umesto sto stampa na ekran jednostavno tura svako resenje u taj tvoj niz nizova, i eto resenja :)

Evo tvog koda prepravljenog u php da vraca ono sto meni treba
Code:

function KombinacijeBezPonavljanja($elemenata, $od)
    {
    $ret = array ();
    $komb = 1;
    
    if (($od >= 1) && ($elemenata >= 1) && ($elemenata <= $od))
        {
        for($i=1; $i <= $elemenata; $i++)
            $ret[$komb][$i] = $i;    // prva kombinacija

        if($elemenata < $od)        // ako ima jos
            {
            $pozicija = $elemenata; // postavi index na zadnji u nizu
            do {
                $ret [++$komb] = $ret [$komb-1];                    // iskopiraj ceo prethodni
                $start = $ret [$komb] [$pozicija] - $pozicija + 1;    // nadji startnu poziciju
                for ($i = $pozicija; $i <= $elemenata; $i++)
                    $ret [$komb][$i] = $start + $i;

                if ($ret [$komb][$elemenata] == $od)    $pozicija--;            // ako je zadnji, umanji indeks za 1
                else                                    $pozicija = $elemenata; // postavi index na zadnji u nizu
                } while ($pozicija > 0);
            }
        return $ret;
        }
    else
        return false;
    }

Goran Pilipović fka bluesman
 
Odgovor na temu

[es] :: Art of Programming :: Algoritam za broj kombinacija bez ponavljanja

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

Postavi temu Odgovori

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