Εισαγωγή
Ένα disjoint set (δομή union-find) κρατά μια συλλογή τιμών χωρισμένη σε μη επικαλυπτόμενες ομάδες και απαντά γρήγορα σε μία ερώτηση: βρίσκονται αυτές οι δύο τιμές στην ίδια ομάδα; Βρίσκεται στο λεξιλόγιο disjoint-sets.
Δημιουργία ενός disjoint set
Το <disjoint-set> δημιουργεί μια κενή δομή. Οι τιμές, τα άτομα, προστίθενται με το add-atom μία κάθε φορά, ή με το add-atoms από μια ακολουθία. Κάθε άτομο ξεκινά σε μια ομάδα μόνο του.
<disjoint-set> ( -- disjoint-set )
add-atom ( atom disjoint-set -- )
add-atoms ( seq disjoint-set -- )
USING: disjoint-sets ;
<disjoint-set>
{ 1 2 3 } over add-atoms ! 1, 2 and 3 each in their own group
Το disjoint set είναι μεταβλητό: το add-atom, το add-atoms και το equate το αλλάζουν επιτόπου αντί να επιστρέφουν ένα νέο. Το keep είναι χρήσιμο όταν θέλεις το disjoint set πίσω στη στοίβα αφού μία από αυτές τις λέξεις το έχει καταναλώσει.
Συγχώνευση ομάδων
Το equate ενώνει τις δύο ομάδες που περιέχουν τα άτομά του. Η ένωση είναι μεταβατική: εξίσωσε δύο άτομα και μετά ένα από αυτά με ένα τρίτο, και τα τρία καταλήγουν σε μία ομάδα.
equate ( atom1 atom2 disjoint-set -- )
Αντιπρόσωποι
Κάθε ομάδα έχει ένα κανονικό μέλος, τον αντιπρόσωπό της. Το representative επιστρέφει τον αντιπρόσωπο, και δύο άτομα ανήκουν στην ίδια ομάδα ακριβώς όταν οι αντιπρόσωποί τους είναι ίσοι.
representative ( atom disjoint-set -- representative )
USING: disjoint-sets ;
<disjoint-set>
{ 1 2 3 } over add-atoms
1 2 pick equate
1 over representative . ! => 1
2 over representative . ! => 1 (same representative as 1)
3 over representative . ! => 3 (still on its own)
Το ποιο άτομο επιλέγει μια ομάδα ως αντιπρόσωπό της είναι εσωτερική λεπτομέρεια. Μην βασίζεσαι ποτέ στο ότι θα επιλεγεί ένα συγκεκριμένο άτομο, μόνο στο ότι δύο άτομα στην ίδια ομάδα συμφωνούν.
Οδηγίες
Η τοπική λέσχη ποίησης ξεκινά μια νέα σεζόν. Οι ποιητές γίνονται μέλη της λέσχης και, όποτε δύο από αυτούς γράφουν μαζί ένα ποίημα, γίνονται μέρος του ίδιου κύκλου συγγραφής. Η λέσχη θέλει να παρακολουθεί ποιος μοιράζεται κύκλο με ποιον, και σου ζήτησαν να γράψεις τις λέξεις που θα το διαχειρίζονται.
Ένα ξένο σύνολο είναι η ιδανική λύση: κάθε ποιητής είναι ένα μεμονωμένο στοιχείο και ένας κύκλος συγγραφής είναι μια ομάδα.
1. Άνοιξε τη λέσχη
Όρισε το new-club, το οποίο παίρνει μια ακολουθία ποιητών και επιστρέφει ένα καινούργιο ξένο σύνολο με όλους τους ποιητές καταχωρισμένους. Κάθε ποιητής ξεκινά σε δικό του κύκλο συγγραφής.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Κατέγραψε μια συνεργασία
Όρισε το collaborate, το οποίο παίρνει δύο ποιητές και μια λέσχη. Συγχωνεύει τους κύκλους συγγραφής των δύο ποιητών και επιστρέφει τη λέσχη, ώστε οι συνεργασίες να καταγράφονται η μία μετά την άλλη.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
! => the club, with Keats and Byron now in one circle
3. Βρες τον κύκλο ενός ποιητή
Όρισε το circle-of, το οποίο παίρνει έναν ποιητή και μια λέσχη και επιστρέφει τον αντιπρόσωπο του κύκλου συγγραφής αυτού του ποιητή. Δύο ποιητές που μοιράζονται κύκλο αναφέρουν πάντα τον ίδιο αντιπρόσωπο.
{ "Keats" "Byron" "Dickinson" } new-club
"Dickinson" swap circle-of
! => "Dickinson" (still in a circle of their own)
4. Μοιράζεσαι κύκλο;
Όρισε το same-circle?, το οποίο παίρνει δύο ποιητές και μια λέσχη και επιστρέφει t όταν και οι δύο ποιητές ανήκουν στον ίδιο κύκλο συγγραφής και f διαφορετικά. Σύγκρινε τους αντιπροσώπους των ποιητών αντί να χρησιμοποιήσεις έναν ενσωματωμένο έλεγχο ισοδυναμίας.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
dup [ "Keats" "Byron" ] dip same-circle? . ! => t
[ "Keats" "Dickinson" ] dip same-circle? . ! => f
Άσκηση εκμάθησης
