Τμήμα Μαθηματικών

Πληροφορική Ι

Εβδομάδα 12 · Απαρίθμηση: Υποσύνολα και Μεταθέσεις

(Οδηγίες χρήσης του διαδραστικού κώδικα: δείτε την αρχική σελίδα.)

1 Απαρίθμηση: Υποσύνολα και Μεταθέσεις

Τώρα που ξέρουμε λίστες και βρόχους for (Εβδομάδα 4), μπορούμε να συνδυάσουμε τις δύο έννοιες για να λύσουμε προβλήματα απαρίθμησης (combinatorics): να μετρήσουμε — και μάλιστα να παράγουμε ρητά — όλα τα δυνατά υποσύνολα ή όλες τις δυνατές διατάξεις ενός συνόλου.

1.1 Πλήθος υποσυνόλων

Έστω ένα σύνολο με \(n\) στοιχεία. Για να φτιάξουμε ένα υποσύνολό του, εξετάζουμε κάθε στοιχείο ένα-ένα και αποφασίζουμε: μέσα ή έξω; Δύο επιλογές για το καθένα από τα \(n\) στοιχεία, ανεξάρτητα μεταξύ τους, δίνουν συνολικά

\[ 2 \times 2 \times \cdots \times 2 = 2^n \]

υποσύνολα (συμπεριλαμβανομένου του κενού συνόλου και ολόκληρου του συνόλου).

Ας γίνουμε πιο ακριβείς. Για κάθε στοιχείο έχουμε μια δυαδική επιλογή: μέσα (1) ή έξω (0). Καταγράφοντας τις \(n\) επιλογές με τη σειρά, παίρνουμε μια λίστα από \(n\) bits — π.χ. για \(n=3\), η [1, 0, 1] σημαίνει «μέσα το 1ο, έξω το 2ο, μέσα το 3ο».

Κάθε λίστα bits αντιστοιχεί σε ένα και μοναδικό υποσύνολο, και αντίστροφα. Άρα τα υποσύνολα είναι ακριβώς όσες και οι λίστες bits μήκους \(n\): \(2^n\).

Αυτό μας δίνει και έναν τρόπο να παράγουμε όλα τα υποσύνολα ρητά: μια λίστα από \(n\) bits δεν είναι τίποτε άλλο από τη δυαδική αναπαράσταση ενός ακεραίου από 0 έως 2**n - 1. Αν λοιπόν αριθμήσουμε όλους αυτούς τους ακέραιους, τα bits της δυαδικής αναπαράστασης του καθενός μας λένε ακριβώς ποια στοιχεία να συμπεριλάβουμε:

flowchart LR
    M["mask = 5<br>δυαδικό 1 0 1"] --> B0["bit 0 = 1 → μέσα το 'a'"]
    M --> B1["bit 1 = 0 → έξω το 'b'"]
    M --> B2["bit 2 = 1 → μέσα το 'c'"]
    B0 --> S["υποσύνολο {a, c}"]
    B1 --> S
    B2 --> S

1.2 Πλήθος μεταθέσεων

Μια μετάθεση (permutation) ενός συνόλου είναι μια διάταξη όλων των στοιχείων του σε κάποια σειρά. Για να φτιάξουμε μια μετάθεση \(n\) στοιχείων: έχουμε \(n\) επιλογές για το ποιο στοιχείο μπαίνει πρώτο, μετά \(n-1\) επιλογές για το δεύτερο (αφού το πρώτο έχει ήδη χρησιμοποιηθεί), κ.ο.κ. Το πλήθος τους είναι επομένως

\[ n \times (n-1) \times (n-2) \times \cdots \times 1 = n!. \]

Μπορούμε να παράγουμε όλες τις μεταθέσεις αναδρομικά (θυμηθείτε την Εβδομάδα 9): μια μετάθεση \(n\) στοιχείων φτιάχνεται επιλέγοντας ποιο στοιχείο μπαίνει πρώτο, και ακολουθώντας το με μια (αναδρομικά παραγόμενη) μετάθεση των υπόλοιπων \(n-1\) στοιχείων. Οι επιλογές σχηματίζουν ένα δέντρο με \(n!\) φύλλα:

flowchart TD
    R["μεταθέσεις του abc"] --> A["a + perm(bc)"]
    R --> B["b + perm(ac)"]
    R --> C["c + perm(ab)"]
    A --> A1["abc"] & A2["acb"]
    B --> B1["bac"] & B2["bca"]
    C --> C1["cab"] & C2["cba"]

Δοκιμάστε να προσθέσετε ένα 4ο ή 5ο στοιχείο στη λίστα elements: το πλήθος των μεταθέσεων εκτοξεύεται (\(4!=24\), \(5!=120\), \(6!=720\), …) πολύ πιο γρήγορα από το πλήθος των υποσυνόλων (\(2^n\)). Σε λογαριθμικό άξονα:

1.3 Χαρακτηριστικό της Python: γεννήτριες για απαρίθμηση, και το module `itertools`

Οι all_subsets και all_permutations φτιάχνουν ολόκληρη τη λίστα αποτελεσμάτων πριν επιστρέψουν οτιδήποτε. Για \(n=20\), αυτό σημαίνει πάνω από ένα εκατομμύριο υποσύνολα (\(2^{20}\)) ταυτόχρονα στη μνήμη — γρήγορα απαγορευτικό.

Μια γεννήτρια (generator, Εβδομάδα 9) το λύνει: παράγει τα υποσύνολα ένα-ένα, «τεμπέλικα», χωρίς ποτέ να τα κρατήσει όλα μαζί:

Αφού η απαρίθμηση υποσυνόλων/μεταθέσεων/συνδυασμών είναι τόσο συνηθισμένο πρόβλημα, η πρότυπη βιβλιοθήκη της Python περιλαμβάνει ήδη έτοιμες, βελτιστοποιημένες γεννήτριες γι’ αυτό ακριβώς, στο module itertools:

Το itertools.combinations(elements, k) παράγει όλα τα υποσύνολα με ακριβώς \(k\) στοιχεία (μια πιο συγκεκριμένη ερώτηση από το “όλα τα υποσύνολα” που λύσαμε παραπάνω με το bit-trick). Όπως και με τον αλγόριθμο του Ευκλείδη στην Εβδομάδα 11: το να ξέρουμε να γράψουμε αυτούς τους αλγορίθμους οι ίδιοι μάς βοηθά να καταλάβουμε πώς δουλεύουν και γιατί το πλήθος τους μεγαλώνει όσο μεγαλώνει — αλλά στην πράξη, το itertools είναι συνήθως η πιο γρήγορη και ασφαλής επιλογή.

1.4 Μια ταυτότητα αθροίσματος δυνάμεων του 2

Αφού το πλήθος των υποσυνόλων ενός συνόλου με \(i\) στοιχεία είναι \(2^i\), τι θα πάρουμε αν αθροίσουμε αυτό το πλήθος για \(i = 1, 2, \ldots, n\); Δηλαδή, ισχύει η ταυτότητα

\[ \sum_{i=1}^{n} 2^i = 2 + 4 + 8 + \cdots + 2^n \;=\; 2^{n+1} - 2 \; ? \]

Μπορούμε να την αποδείξουμε μαθηματικά (είναι το άθροισμα γεωμετρικής προόδου), αλλά μπορούμε επίσης να την επαληθεύσουμε υπολογιστικά για κάθε \(n\) μέχρι, ας πούμε, το \(20\), υπολογίζοντας και τις δύο πλευρές ανεξάρτητα και συγκρίνοντάς τες:

Αυτού του είδους η υπολογιστική επαλήθευση δεν αποτελεί μαθηματική απόδειξη (ελέγχει μόνο πεπερασμένες, συγκεκριμένες περιπτώσεις — εδώ \(n \le 20\)), αλλά είναι εξαιρετικά χρήσιμη: μας δίνει άμεση εμπιστοσύνη ότι μια ταυτότητα “φαίνεται σωστή” προτού μπούμε στον κόπο μιας αυστηρής απόδειξης, και βοηθάει να εντοπίσουμε γρήγορα λάθος τύπους.

2 Σύνοψη

Σε αυτή την εβδομάδα είδαμε:

Πώς να μετράμε και να παράγουμε συνδυαστικά αντικείμενα με αντιστοίχιση σε δυαδική αναπαράσταση ακεραίων (bitmask).
Πώς να παράγουμε συνδυαστικά αντικείμενα αναδρομικά.
Γεννήτριες για απαρίθμηση χωρίς αποθήκευση όλων των αποτελεσμάτων ταυτόχρονα, και το module itertools.
Την τεχνική της υπολογιστικής επαλήθευσης μιας ταυτότητας σε πολλές περιπτώσεις, πριν από μια αυστηρή απόδειξη.

⤺ Πίσω στην αρχική σελίδα / πρόγραμμα μαθήματος · Διαφάνειες αυτής της εβδομάδας