Mixtape-Macher

Das Vokabular math.combinatorics beantwortet zwei Arten von Fragen zu einer Sammlung von Elementen:

• Kombinationen: Auf wie viele Arten, oder auf welche Arten, kannst du eine Gruppe auswählen, wobei die Reihenfolge keine Rolle spielt?
• Permutationen: Auf wie viele Arten, oder auf welche Arten, kannst du Elemente anordnen, wobei die Reihenfolge zählt?

Zu jeder Frage gibt es ein zählendes Wort, das eine Zahl zurückgibt, und ein auflistendes Wort, das die tatsächlichen Auswahlen zurückgibt.

Zählen

nCk („n wähle k") gibt zurück, wie viele k-elementige Kombinationen aus n Elementen ausgewählt werden können:

nCk ( n k -- m )

USING: math.combinatorics prettyprint ;

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

nPk gibt zurück, wie viele geordnete Auswahlen (Permutationen) mit k Elementen aus n Elementen gebildet werden können. Da die Reihenfolge zählt, ist die Anzahl mindestens so groß wie die des passenden nCk:

nPk ( n k -- m )

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

Kombinationen auflisten

all-combinations gibt jede k-elementige Teilmenge einer Sequenz zurück. Die Elemente innerhalb jeder Kombination behalten ihre ursprüngliche Reihenfolge, und die Kombinationen kommen in lexikografischer Reihenfolge zurück:

all-combinations ( seq k -- combinations )

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

Wenn du jede Kombination nur verarbeiten willst, während sie entsteht, statt sie alle zu sammeln, dann verwende die streamende Form each-combination, die ein Quotation mit jeder Kombination aufruft:

each-combination ( seq k quot -- )

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

Permutationen auflisten

all-permutations gibt jede Anordnung einer Sequenz zurück:

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

Ihr streamendes Gegenstück ist each-permutation, das ein Quotation mit jeder Anordnung aufruft:

each-permutation ( seq quot -- )

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