☰

» »

Kako izračunati št. kombinacij

Kako izračunati št. kombinacij

c0dehunter ::

Recimo, da imamo tri črke - a, b, c. Iz teh treh črk bi rad dobil vse možne kombinacije, pri čemer je ena kombinacija iz dveh znakov. Torej, če začnem: ab, ac, aa, ba, ca, ...

Zanima me kako bi izračunal koliko je možnih kombinacij? Tukaj bi kombinatorika lepo zraven pomagala, ampak nisem prepričan kaj potrebujem - sklepam pa da permutacijo.
I do not agree with what you have to say,
but I'll defend to the death your right to say it.

zee ::

Rabis kombinacijo...iz mnozice treh elementov izbiras dva.
zee
Linux: Be Root, Windows: Re Boot
Giant Amazon and Google Compute Cloud in the Sky.

black ice ::

Permutacije bi lahko uporabil če bi imel število mest enako številu elementov. Ker so elementi različni ne moreš uporabiti niti permutacij s ponavljanjem. Kar ti rabiš so kombinacije s ponavljanjem, oz. neurejene nize dolžine r, v katerih se določen element lahko pojavi večkrat.
(p)Crn+r+1 = ( n + r + 1 / r )

Vendar pazi: to ni navaden oklepaj ampak binom! Pri čemer je n število elementov v množici (v tvojem primeru 3) in r številu mest (2), ki so na voljo.

c0dehunter ::

Še zmeraj pa ne dobim pravega števila kombinacij.

Če še enkrat pokažem na prvem primeru (3 črke, ena kombinacija je iz dveh črk):

C=(3+2-1 / 2) - binomski simbol, ne ulomkova črta
C=(4 / 2)
C= 4*3 / 2*1
C= 6

Kar pa seveda ne drži, ker je kombinacij 9. Kje sm ga ušpiču?
I do not agree with what you have to say,
but I'll defend to the death your right to say it.

zee ::

Binomski simbol je, ce imas kombinacije brez ponavljanja (ab = ba). Za kombinacije s ponavljanjem se pa ne spomnem.
zee
Linux: Be Root, Windows: Re Boot
Giant Amazon and Google Compute Cloud in the Sky.

dragana ::

Načeloma to izračunaš tako, da se vprašaš:
-koliko izbire imaš za prvo mesto? odgovor je 3
-koliko izbire je za drugo mesto? odgovor je spet 3 (ker se elementi lahko ponavljajo)
izračun je zmnožek obeh izbir: 3x3=9

joze67 ::

Za prvo mesto v dvomestni kombinaciji imaš ... tri možnosti. Za drugo mesto imaš ... tri možnosti. Skupaj, 9. Nizi so pač urejeni.

jernejp ::

Število znakov ^ Število mest v kombinaciji
3^2=9

podobno kot binarno ali desetiško...

c0dehunter ::

Aha, hvala!
Sicer sem za tale primer vedel da dobiš št. kombinacij z n2, ampak nism bil sigurn če to potem deluje tudi za drugačne cifre (recimo 4 črke in 2 v eni komb.).
I do not agree with what you have to say,
but I'll defend to the death your right to say it.

ta_ki_tke ::

Kombinacije s ponavljanjem, kjer je AB enako BA, torej ne glede na vrstni red, bi bile to, kar je svetoval Black Ice (le da je namesto - napisal +), ti pa potrebuješ variacije s ponavljanjem.
http://web.mef.hr/if/alati/racunala/skr...

black ice ::

Double fail. ;((
Pari so urejeni, torej variacije s ponavljanjem. Drugič bom raje dvakrat premislil preden kaj napišem.

c0dehunter ::

Tkalec, hvala ;)
black ice, vsak se lahko zmoti :)

Sicer pa sprašujem ker moram narediti program (v C++), ki bo izpisal vse možne kombinacije, pri čemer uporabnik vpiše (različne) črke in koliko elementov ima lahko ena kombinacija.
Seveda razumem da se večini ne da tole študirat, ampak če se kje najde kdo z kako idejo kako to narediti pa le na plano z njo :)
Sam sem najprej poskusil z dvodimenzionalno tabelo in sem potem filal črke na ustrezna mesta. Škoda, da sem se šele proti koncu spomnil da ni nujno da bo uporabnik vedno rekel da naj bosta dva elementa v vsaki kombinaciji :))
Sicer pa ravnokar razmišljam z razširitvijo tabele, ampak bom videl kako bo.
I do not agree with what you have to say,
but I'll defend to the death your right to say it.

Zgodovina sprememb…

black ice ::

Primer za 3 elemente kombinacij reda 2

Možne kombinacije: aa, ab, ac, bb, ba, bc, cc, ca, cb.

Jaz bi najprej naredil takole: shranil vse elemente posamezno v neko polje in nato izpisal samo kombinacije, ki vsebujejo samo en element (aa,bb,cc) - indeksi v polju kombinacije bi bili naslednji: a = 0 ; b = 1; c = 2

Nato bi ikrementiral indeks v polju drugega elementa kombinacije (elementa na drugem - v tem primeru zadnjem mestu kombinacije), da bi dobil kombinaciji ab in ac. Ponovil bi za prvi element kombinacije, da bi dobil kombinaciji ba in bc. Ostane le še ca in cb, ostale (aa,bb,cc) smo že izpisali.

Žal nimam dovolj podlage v c++ da bi ti povedal kako izpisati en element n-krat oziroma tolikokrat koliko mest ima kombinacija. Mogoče bi lahko kako rešil z zanko? Nimam pojma, samo ugibam.

V bistvu bi princip lahko uporabil tudi za n-mestno kombinacijo, nadaljuješ dokler ne prideš do zadnje ikrementacije zadnjega elementa, vmes pa preveriš če si res izpisal vse kombinacije.

Upam, da se ti utrne kakšna ideja. Pa prosim prilepi rešitev ker me zanima kako boš rešil.

boogie_xlr ::

programiranje II prva bonus naloga :))
ne se matrat, za kombinacije dveh črk nardiš zanko v zanki(n^2), za kombinacije treh črk pa zanko v zanki, ki je v zanki(n^3).

c0dehunter ::

boogie_xlr je izjavil:

programiranje II prva bonus naloga :))

Heheh, potencialen sošolc? :))

Hvala za obe ideji, bom probal tole čez vikend nardit pa sporočim.
I do not agree with what you have to say,
but I'll defend to the death your right to say it.

milc ::

Evo z rekurzijo:
sub var {
  my ($n, $el, @elementi) = @_;
  $el = $el // "";
  state $stevec = 0;
  if ($n > 0) {
    foreach my $element (@elementi) {
      # rekuzija
      $stevec = &var($n - 1, "${el}${element}", @elementi);  
    }
  } else {  
    say $el;
    $stevec++;
  } # else
  return $stevec;
} # var

my @el = ("a","b","c");
say "stevec = " . &var(2, undef, @el);

Rezultat:
aa
ab
ac
ba
bb
bc
ca
cb
cc
stevec = 9

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Kombinatorika

Oddelek: Šola		192015 (1356) 2f4u
»

[c++] naloge

Oddelek: Programiranje		476237 (4777) technolog
»

Par nalog iz verjetnosti ("osnovne")

Oddelek: Šola		61184 (958) tinkatinca
»

pomoč pri nalogi - kombinatorika

Oddelek: Šola		71512 (1334) PaX_MaN
»

matematika pomoč(kombinatorika)(matura)

Oddelek: Šola		377048 (6630) starsplash

Več podobnih tem