Πληροφορική Ι — Εβδομάδα 12

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

Υποσύνολα: δυαδική αναπαράσταση

Κάθε στοιχείο: μέσα (1) ή έξω (0) → μια λίστα \(n\) bits ↔︎ ένας ακέραιος \(0 \ldots 2^n{-}1\):

def all_subsets(elements):
    n = len(elements)
    subsets = []
    for mask in range(2 ** n):
        subset = [elements[i] for i in range(n) if (mask >> i) & 1]
        subsets.append(subset)
    return subsets

\(2^n\) υποσύνολα συνολικά.

Μεταθέσεις: αναδρομικά

flowchart TD
    R["perm(abc)"] --> A["a + perm(bc)"] & B["b + perm(ac)"] & C["c + perm(ab)"]
    A --> A1["abc"] & A2["acb"]
    B --> B1["bac"] & B2["bca"]
    C --> C1["cab"] & C2["cba"]

Για κάθε δυνατό πρώτο στοιχείο, μεταθέτουμε αναδρομικά τα υπόλοιπα:

def all_permutations(elements):
    if len(elements) <= 1:
        return [elements]
    perms = []
    for i in range(len(elements)):
        first = elements[i]
        rest = elements[:i] + elements[i+1:]
        for p in all_permutations(rest):
            perms.append([first] + p)
    return perms

\(n!\) μεταθέσεις — μεγαλώνει πολύ πιο γρήγορα από το \(2^n\).

Γεννήτριες & `itertools`

Χωρίς να αποθηκεύσουμε όλα τα αποτελέσματα ταυτόχρονα.

Υπολογιστική επαλήθευση ταυτότητας

Έλεγχος σε πολλές περιπτώσεις, πριν/αντί για αυστηρή απόδειξη.

Σύνοψη

Υποσύνολα μέσω δυαδικής αναπαράστασης (bitmask)
Μεταθέσεις αναδρομικά
Γεννήτριες για απαρίθμηση, module itertools
Υπολογιστική επαλήθευση μιας ταυτότητας