Creatore di mixtape

Il vocabolario math.combinatorics risponde a due tipi di domande su una collezione di elementi:

• Combinazioni: in quanti modi, o in quali modi, puoi scegliere un gruppo, ignorando l'ordine?
• Permutazioni: in quanti modi, o in quali modi, puoi disporre gli elementi, dove l'ordine conta?

Per ciascuna domanda c'è una parola di conteggio che restituisce un numero e una parola di elencazione che restituisce le selezioni effettive.

Conteggio

nCk («n choose k») restituisce quante combinazioni di k elementi si possono scegliere da n elementi:

nCk ( n k -- m )

USING: math.combinatorics prettyprint ;

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

nPk restituisce quante selezioni ordinate di k elementi (permutazioni) si possono fare da n elementi. Poiché l'ordine conta, il conteggio è almeno pari a quello del corrispondente nCk:

nPk ( n k -- m )

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

Elencare le combinazioni

all-combinations restituisce ogni sottoinsieme di k elementi di una sequenza. Gli elementi all'interno di ciascuna combinazione mantengono il loro ordine originale, e le combinazioni vengono restituite in ordine lessicografico:

all-combinations ( seq k -- combinations )

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

Quando vuoi elaborare ogni combinazione man mano che viene prodotta, invece di raccoglierle tutte, usa la forma in streaming each-combination, che chiama una quotation con ciascuna combinazione:

each-combination ( seq k quot -- )

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

Elencare le permutazioni

all-permutations restituisce ogni ordinamento di una sequenza:

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

La sua controparte in streaming è each-permutation, che chiama una quotation con ciascun ordinamento:

each-permutation ( seq quot -- )

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