Algoritam za broj kombinacija bez ponavljanja

Algoritam za broj kombinacija bez ponavljanja 12.08.2002. u 02:11 · pre 295 meseci #1

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?

Potpis

Goran Pilipović fka bluesman

Re: Algoritam za broj kombinacija bez ponavljanja 12.08.2002. u 16:37 · pre 295 meseci #2

sta se desava? Niko nema cak ni ideju?

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

Potpis

Goran Pilipović fka bluesman

Re: Algoritam za broj kombinacija bez ponavljanja 13.08.2002. u 04:51 · pre 295 meseci #3

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.

Re: Algoritam za broj kombinacija bez ponavljanja 13.08.2002. u 19:01 · pre 295 meseci #4

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

Pozdrav.

Re: Algoritam za broj kombinacija bez ponavljanja 13.08.2002. u 21:11 · pre 295 meseci #5

Krsto, ajde daj taj kod, i mene interesuje.

pozdrav

Potpis

fire, walk with me

Re: Algoritam za broj kombinacija bez ponavljanja 14.08.2002. u 01:35 · pre 295 meseci #6

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)

Re: Algoritam za broj kombinacija bez ponavljanja 14.08.2002. u 03:49 · pre 295 meseci #7

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

Re: Algoritam za broj kombinacija bez ponavljanja 14.08.2002. u 05:32 · pre 295 meseci #8

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

Re: Algoritam za broj kombinacija bez ponavljanja 14.08.2002. u 12:54 · pre 295 meseci #9

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 ?

Potpis

fire, walk with me

Re: Algoritam za broj kombinacija bez ponavljanja 16.08.2002. u 19:25 · pre 294 meseca #10

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

Potpis

Goran Pilipović fka bluesman

Re: Algoritam za broj kombinacija bez ponavljanja 21.08.2002. u 14:19 · pre 294 meseca #11

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

komb.c0.89k

Re: Algoritam za broj kombinacija bez ponavljanja 21.08.2002. u 16:25 · pre 294 meseca #12

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

Potpis

Goran Pilipović fka bluesman

Re: Algoritam za broj kombinacija bez ponavljanja 21.08.2002. u 17:37 · pre 294 meseca #13

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

Re: Algoritam za broj kombinacija bez ponavljanja 21.08.2002. u 17:50 · pre 294 meseca #14

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

Potpis

Goran Pilipović fka bluesman

Re: Algoritam za broj kombinacija bez ponavljanja 21.08.2002. u 23:00 · pre 294 meseca #15

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

Re: Algoritam za broj kombinacija bez ponavljanja 23.08.2002. u 15:19 · pre 294 meseca #16

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

Potpis

Goran Pilipović fka bluesman

Forum kao aplikacija na telefonu

Srodne teme