A math.combinatorics szótár kétféle kérdésre ad választ egy elemhalmazzal kapcsolatban:
-
Kombinációk: hányféleképpen, illetve mely módokon tudsz kiválasztani egy csoportot, figyelmen kívül hagyva a sorrendet?
-
Permutációk: hányféleképpen, illetve mely módokon tudsz elrendezni elemeket, ahol a sorrend számít?
Mindkét kérdéshez tartozik egy számláló szó, amely egy számot ad vissza, és egy listázó szó, amely a tényleges kiválasztásokat adja vissza.
Számlálás
Az nCk („n alatt a k”) visszaadja, hogy hány k elemű kombináció választható ki n elemből:
nCk ( n k -- m )
USING: math.combinatorics prettyprint ;
5 2 nCk . ! => 10
6 3 nCk . ! => 20
5 5 nCk . ! => 1
Az nPk visszaadja, hogy hány k elemű sorrenddel bíró kiválasztás (permutáció) képezhető n elemből. Mivel itt számít a sorrend, a darabszám legalább akkora, mint a hozzá tartozó nCk értéke:
nPk ( n k -- m )
5 2 nPk . ! => 20
6 3 nPk . ! => 120
Kombinációk listázása
Az all-combinations visszaadja egy sorozat minden k elemű részhalmazát. Az egyes kombinációkon belüli elemek megőrzik eredeti sorrendjüket, a kombinációk pedig lexikografikus sorrendben jönnek vissza:
all-combinations ( seq k -- combinations )
{ 1 2 3 } 2 all-combinations .
! => { { 1 2 } { 1 3 } { 2 3 } }
Ha minden kombinációt csak akkor szeretnél feldolgozni, amikor épp létrejön, ahelyett hogy az összeset összegyűjtenéd, használd a streamelő formát, az each-combination szót, amely minden kombinációval meghív egy quotationt:
each-combination ( seq k quot -- )
{ 1 2 3 } 2 [ . ] each-combination
! => { 1 2 }
! => { 1 3 }
! => { 2 3 }
Permutációk listázása
Az all-permutations visszaadja egy sorozat minden lehetséges sorrendjét:
all-permutations ( seq -- permutations )
{ 1 2 } all-permutations .
! => { { 1 2 } { 2 1 } }
{ 1 2 3 } all-permutations .
! => { { 1 2 3 } { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 1 2 } { 3 2 1 } }
A streamelő megfelelője az each-permutation, amely minden sorrenddel meghív egy quotationt:
each-permutation ( seq quot -- )
{ 1 2 } [ . ] each-permutation
! => { 1 2 }
! => { 2 1 }
Tanulófeladat
