Το vocabulary math.combinatorics απαντά σε δύο
είδη ερωτήσεων για μια συλλογή στοιχείων:
-
Συνδυασμοί: πόσοι τρόποι, ή ποιοι τρόποι, υπάρχουν για να
επιλέξεις μια ομάδα, αγνοώντας τη σειρά;
-
Μεταθέσεις: πόσοι τρόποι, ή ποιοι τρόποι, υπάρχουν για να
τακτοποιήσεις στοιχεία, όπου η σειρά έχει σημασία;
Για κάθε ερώτηση υπάρχει μια λέξη μέτρησης που επιστρέφει έναν αριθμό
και μια λέξη απαρίθμησης που επιστρέφει τις ίδιες τις επιλογές.
Μέτρηση
Το nCk ("n διαλέγεις k") επιστρέφει πόσους συνδυασμούς k στοιχείων
μπορείς να επιλέξεις από n στοιχεία:
nCk ( n k -- m )
USING: math.combinatorics prettyprint ;
5 2 nCk . ! => 10
6 3 nCk . ! => 20
5 5 nCk . ! => 1
Το nPk επιστρέφει πόσες διατεταγμένες επιλογές (μεταθέσεις) k
στοιχείων μπορούν να γίνουν από n στοιχεία. Επειδή η σειρά έχει
σημασία, ο αριθμός είναι τουλάχιστον όσο μεγάλος όσο ο αντίστοιχος nCk:
nPk ( n k -- m )
5 2 nPk . ! => 20
6 3 nPk . ! => 120
Απαρίθμηση συνδυασμών
Το all-combinations επιστρέφει κάθε υποσύνολο k στοιχείων μιας
ακολουθίας. Τα στοιχεία μέσα σε κάθε συνδυασμό διατηρούν την αρχική τους
σειρά, και οι συνδυασμοί επιστρέφονται σε λεξικογραφική σειρά:
all-combinations ( seq k -- combinations )
{ 1 2 3 } 2 all-combinations .
! => { { 1 2 } { 1 3 } { 2 3 } }
Όταν θέλεις να επεξεργάζεσαι κάθε συνδυασμό καθώς παράγεται, αντί να
τους συγκεντρώνεις όλους, χρησιμοποίησε τη μορφή ροής
each-combination, η οποία καλεί ένα quotation με κάθε συνδυασμό:
each-combination ( seq k quot -- )
{ 1 2 3 } 2 [ . ] each-combination
! => { 1 2 }
! => { 1 3 }
! => { 2 3 }
Το all-permutations επιστρέφει κάθε διάταξη μιας ακολουθίας:
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 } }
Το αντίστοιχό του στη μορφή ροής είναι το each-permutation, το οποίο
καλεί ένα quotation με κάθε διάταξη:
each-permutation ( seq quot -- )
{ 1 2 } [ . ] each-permutation
! => { 1 2 }
! => { 2 1 }
Άσκηση εκμάθησης
