[es] - Algoritam za broj kombinacija bez ponavljanja

bluesman
Goran Pilipović
Beograd

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

ICQ: 7987706
Sajt: www.revolution.co.yu

Profil

Algoritam za broj kombinacija bez ponavljanja

^{12.08.2002. u 01:11}

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

^{12.08.2002. u 01:11}

bluesman
Goran Pilipović
Beograd

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

ICQ: 7987706
Sajt: www.revolution.co.yu

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{12.08.2002. u 15:37}

sta se desava? Niko nema cak ni ideju?

Ne ocekujem da mi se napise ceo algoritam, bar neka ideja.

Goran Pilipović fka bluesman

^{12.08.2002. u 15:37}

Milos^
Beograd

Član broj: 4596
Poruke: 11
195.250.105.*

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{13.08.2002. u 03:51}

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.

^{13.08.2002. u 03:51}

Krsta
Krstic Dejan
Licna firma za izradu i projektovanje inf. sistema, r..
Krusevac

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

Sajt: www.illusion.co.yu

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{13.08.2002. u 18:01}

Imam Source code radjen u VB-u, posto sam i ja imao slican problem. Ako ti nesto znaci postovacu ovde.

Pozdrav.

Ako neznas kuda ides, sigurno ces tamo da stignes !!!

"Digital ILLUSION" - Krusevac
www.illusion.co.yu

^{13.08.2002. u 18:01}

jc denton

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

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{13.08.2002. u 20:11}

Krsto, ajde daj taj kod, i mene interesuje.

pozdrav

...za sada samo citam.

^{13.08.2002. u 20:11}

srki
Srdjan Mitrovic
Auckland, N.Z.

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

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{14.08.2002. u 00:35}

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)

^{14.08.2002. u 00:35}

Krsta
Krstic Dejan
Licna firma za izradu i projektovanje inf. sistema, r..
Krusevac

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

Sajt: www.illusion.co.yu

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{14.08.2002. u 02:49}

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...

Ako neznas kuda ides, sigurno ces tamo da stignes !!!

"Digital ILLUSION" - Krusevac
www.illusion.co.yu

^{14.08.2002. u 02:49}

Milos^
Beograd

Član broj: 4596
Poruke: 11
195.250.105.*

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{14.08.2002. u 04:32}

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));

^{14.08.2002. u 04:32}

jc denton

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

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{14.08.2002. u 11:54}

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 ?

...za sada samo citam.

^{14.08.2002. u 11:54}

bluesman
Goran Pilipović
Beograd

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

ICQ: 7987706
Sajt: www.revolution.co.yu

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{16.08.2002. u 18:25}

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 j****i 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

^{16.08.2002. u 18:25}

mucky
Aleksandar Mastilović
Novi Sad - Srbija

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

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{21.08.2002. u 13:19}

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

komb.c - 0.89k

^{21.08.2002. u 13:19}

bluesman
Goran Pilipović
Beograd

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

ICQ: 7987706
Sajt: www.revolution.co.yu

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{21.08.2002. u 15:25}

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

^{21.08.2002. u 15:25}

mucky
Aleksandar Mastilović
Novi Sad - Srbija

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

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{21.08.2002. u 16:37}

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

^{21.08.2002. u 16:37}

bluesman
Goran Pilipović
Beograd

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

ICQ: 7987706
Sajt: www.revolution.co.yu

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{21.08.2002. u 16:50}

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

^{21.08.2002. u 16:50}

srki
Srdjan Mitrovic
Auckland, N.Z.

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

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{21.08.2002. u 22:00}

I moje resenje moze da prepravi da umesto stampanja samo smesta u niz.
Je l' si probao da startujes ono moje?

^{21.08.2002. u 22:00}

bluesman
Goran Pilipović
Beograd

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

ICQ: 7987706
Sajt: www.revolution.co.yu

Profil

Re: Algoritam za broj kombinacija bez ponavljanja

^{23.08.2002. u 14:19}

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

^{23.08.2002. u 14:19}