Chapter 11 — Sets and Basic Set Operations

# --- Visualization: Venn diagrams for set operations ---
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
plt.style.use('seaborn-v0_8-whitegrid')

fig, axes = plt.subplots(2, 3, figsize=(15, 8))
fig.patch.set_facecolor('white')

ops = [
    ('Union A ∪ B', 'steelblue', 'steelblue'),
    ('Intersection A ∩ B', None, None),
    ('Difference A \ B', 'steelblue', None),
    ('Difference B \ A', None, 'coral'),
    ('Symmetric Diff A △ B', 'both_excl', None),
    ('Complement Aᶜ (in U)', 'complement', None),
]

for ax, (title, left_col, right_col) in zip(axes.flat, ops):
    ax.set_xlim(-2, 5)
    ax.set_ylim(-1.5, 2)
    ax.set_aspect('equal')
    ax.axis('off')
    ax.set_title(title, fontsize=10, pad=4)
    
    if title.startswith('Complement'):
        universe = patches.Rectangle((-1.8, -1.3), 6.6, 3.2, linewidth=1.5,
                                       edgecolor='black', facecolor='lightyellow', alpha=0.5)
        ax.add_patch(universe)
        circle_a = plt.Circle((1.3, 0.3), 0.9, color='steelblue', alpha=0.6)
        ax.add_patch(circle_a)
        ax.text(1.3, 0.3, 'A', ha='center', va='center', fontsize=12, color='white', fontweight='bold')
        ax.text(-0.8, 1.2, 'Aᶜ', ha='center', va='center', fontsize=11, color='dimgray')
        continue
    
    # Left and right circles
    for cx, color, label in [(1.0, 'steelblue', 'A'), (2.5, 'coral', 'B')]:
        fill = None
        if title.startswith('Union'):
            fill = color
        elif title.startswith('Intersection'):
            fill = None
        elif title == 'Difference A \ B' and label == 'A':
            fill = 'steelblue'
        elif title == 'Difference B \ A' and label == 'B':
            fill = 'coral'
        alpha = 0.45 if fill else 0.12
        circle = plt.Circle((cx, 0.3), 0.95, color=fill or 'gray', alpha=alpha, linewidth=1.5, edgecolor='black', fill=True)
        ax.add_patch(circle)
        ax.text(cx, -0.9, label, ha='center', va='center', fontsize=13, fontweight='bold')
    
    # Intersection overlay
    if title.startswith('Intersection'):
        from matplotlib.patches import PathPatch
        circle_i = plt.Circle((1.75, 0.3), 0.6, color='purple', alpha=0.6)
        ax.add_patch(circle_i)
    elif title.startswith('Symmetric'):
        circle_l = plt.Circle((1.0, 0.3), 0.95, color='steelblue', alpha=0.5, linewidth=1.5, edgecolor='black')
        circle_r = plt.Circle((2.5, 0.3), 0.95, color='coral', alpha=0.5, linewidth=1.5, edgecolor='black')
        circle_mid = plt.Circle((1.75, 0.3), 0.6, color='white', alpha=1.0)
        ax.add_patch(circle_l); ax.add_patch(circle_r); ax.add_patch(circle_mid)
    elif title == 'Difference A \ B':
        circle_overlap = plt.Circle((1.75, 0.3), 0.6, color='white', alpha=1.0)
        ax.add_patch(circle_overlap)

plt.suptitle('Set Operations — Venn Diagram Representations', fontsize=12)
plt.tight_layout()
plt.show()

# --- Implementation: Set operations from scratch and verification ---
import numpy as np

class MathSet:
    """
    Immutable mathematical set with standard operations.
    Built on Python frozenset for correctness guarantees.
    """
    def __init__(self, elements):
        self._data = frozenset(elements)
    
    def __contains__(self, x): return x in self._data
    def __len__(self): return len(self._data)
    def __repr__(self): return '{' + ', '.join(str(x) for x in sorted(self._data)) + '}'
    def __eq__(self, other): return self._data == other._data
    
    def union(self, other):        return MathSet(self._data | other._data)
    def intersection(self, other): return MathSet(self._data & other._data)
    def difference(self, other):   return MathSet(self._data - other._data)
    def sym_diff(self, other):     return MathSet(self._data ^ other._data)
    def is_subset(self, other):    return self._data <= other._data
    def power_set(self):
        from itertools import combinations
        elems = list(self._data)
        result = [MathSet([])]
        for r in range(1, len(elems)+1):
            for combo in combinations(elems, r):
                result.append(MathSet(combo))
        return result

A = MathSet([1, 2, 3, 4, 5])
B = MathSet([3, 4, 5, 6, 7])

print(f'A = {A}')
print(f'B = {B}')
print(f'A ∪ B = {A.union(B)}')
print(f'A ∩ B = {A.intersection(B)}')
print(f'A \ B = {A.difference(B)}')
print(f'A △ B = {A.sym_diff(B)}')
print(f'A ⊆ A ∪ B: {A.is_subset(A.union(B))}')

C = MathSet([1, 2, 3])
print(f'\nPower set of {C}:')
for s in C.power_set():
    print(f'  {s}')
print(f'|P(C)| = {len(C.power_set())}  (expected: 2^3 = 8)')

# --- Experiment: Verify set laws computationally ---
import random
random.seed(42)

UNIVERSE = list(range(100))

def random_set():
    return MathSet(random.sample(UNIVERSE, random.randint(5, 40)))

N_TESTS = 1000
laws = {
    'Commutativity (union)': lambda A,B,C: A.union(B) == B.union(A),
    'Commutativity (intersect)': lambda A,B,C: A.intersection(B) == B.intersection(A),
    'Associativity (union)': lambda A,B,C: (A.union(B)).union(C) == A.union(B.union(C)),
    'Distributivity': lambda A,B,C: A.intersection(B.union(C)) == (A.intersection(B)).union(A.intersection(C)),
    'A ∩ A = A': lambda A,B,C: A.intersection(A) == A,
    'A ∪ ∅ = A': lambda A,B,C: A.union(MathSet([])) == A,
}

print('Set law verification (1000 random tests each):')
for name, law in laws.items():
    passed = sum(1 for _ in range(N_TESTS) if law(random_set(), random_set(), random_set()))
    print(f'  {name}: {passed}/{N_TESTS}  {"✓" if passed==N_TESTS else "✗"} ')

# --- Mini Project: Set-based feature engineering ---
# Represent ML training/test split and feature selection as set operations.
import numpy as np

np.random.seed(42)
N = 200
all_ids = set(range(N))

# Train/test split as set partition
train_ids = set(np.random.choice(N, int(0.8*N), replace=False))
test_ids  = all_ids - train_ids  # A \ B
validation_ids = set(np.random.choice(list(train_ids), int(0.1*N), replace=False))
train_only = train_ids - validation_ids

print('Dataset partitioning via set operations:')
print(f'  Total samples: {len(all_ids)}')
print(f'  Train:         {len(train_only)}')
print(f'  Validation:    {len(validation_ids)}')
print(f'  Test:          {len(test_ids)}')
print(f'  Sum:           {len(train_only)+len(validation_ids)+len(test_ids)}')
print(f'  Disjoint (no overlap): {len(train_only & validation_ids & test_ids) == 0}')
print(f'  Cover (union = all):   {train_only | validation_ids | test_ids == all_ids}')