Algoritam za broj kombinacija bez ponavljanja

[ bluesman @ 12.08.2002. 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?

[ bluesman @ 12.08.2002. 15:37 ] @

sta se desava? Niko nema cak ni ideju?

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

[ Milos^ @ 13.08.2002. 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.

[ Krsta @ 13.08.2002. 18:01 ] @

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

Pozdrav.

[ jc denton @ 13.08.2002. 20:11 ] @

Krsto, ajde daj taj kod, i mene interesuje.

pozdrav

[ srki @ 14.08.2002. 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)

[ Krsta @ 14.08.2002. 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...

[ Milos^ @ 14.08.2002. 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));

[ jc denton @ 14.08.2002. 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 ?

[ bluesman @ 16.08.2002. 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 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));
}

[ mucky @ 21.08.2002. 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

[ bluesman @ 21.08.2002. 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

[ mucky @ 21.08.2002. 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

[ bluesman @ 21.08.2002. 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

[ srki @ 21.08.2002. 22:00 ] @

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

[ bluesman @ 23.08.2002. 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;
    }