Le créateur de mixtapes

Le vocabulaire math.combinatorics répond à deux types de questions sur une collection d'éléments :

• Combinaisons : de combien de façons, ou de quelles façons, peut-on choisir un groupe, sans tenir compte de l'ordre ?
• Permutations : de combien de façons, ou de quelles façons, peut-on disposer les éléments, quand l'ordre compte ?

Pour chaque question, il existe un mot de dénombrement qui renvoie un nombre et un mot d'énumération qui renvoie les sélections elles-mêmes.

Dénombrement

nCk (« n choisit k ») renvoie le nombre de combinaisons de k éléments que l'on peut choisir parmi n éléments :

nCk ( n k -- m )

USING: math.combinatorics prettyprint ;

5 2 nCk .    ! => 10
6 3 nCk .    ! => 20
5 5 nCk .    ! => 1

nPk renvoie le nombre de sélections ordonnées (permutations) de k éléments que l'on peut former à partir de n éléments. Comme l'ordre compte, ce total est au moins aussi grand que celui de nCk correspondant :

nPk ( n k -- m )

5 2 nPk .    ! => 20
6 3 nPk .    ! => 120

Liste les combinaisons

all-combinations renvoie tous les sous-ensembles de k éléments d'une séquence. Les éléments à l'intérieur de chaque combinaison conservent leur ordre d'origine, et les combinaisons sont renvoyées dans l'ordre lexicographique :

all-combinations ( seq k -- combinations )

{ 1 2 3 } 2 all-combinations .
! => { { 1 2 } { 1 3 } { 2 3 } }

Quand tu veux seulement traiter chaque combinaison au fur et à mesure qu'elle est produite, plutôt que de les collecter toutes, utilise la forme en flux each-combination, qui appelle une quotation avec chaque combinaison :

each-combination ( seq k quot -- )

{ 1 2 3 } 2 [ . ] each-combination
! => { 1 2 }
! => { 1 3 }
! => { 2 3 }

Liste les permutations

all-permutations renvoie tous les ordres possibles d'une séquence :

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

Son équivalent en flux est each-permutation, qui appelle une quotation avec chaque ordre :

each-permutation ( seq quot -- )

{ 1 2 } [ . ] each-permutation
! => { 1 2 }
! => { 2 1 }