Python Sets

Python Sets: Hash-Based Collections & Set Theory

Sets are unordered collections of unique, hashable objects. Built using hash tables under the hood, sets provide $O(1)$ time complexity for membership testing (x in set), insertions, and deletions.

Set Theory Operations

flowchart TD
    A["Set A: {1, 2, 3}"] --- B["Intersection &"]
    C["Set B: {3, 4, 5}"] --- B
    B --> D["Result: {3}"]
    
    A --- E["Union |"]
    C --- E
    E --> F["Result: {1, 2, 3, 4, 5}"]

Set Operations Reference

• Union (setA | setB or setA.union(setB)): Elements in either set.
• Intersection (setA & setB or setA.intersection(setB)): Elements in both sets.
• Difference (setA - setB or setA.difference(setB)): Elements in setA but not setB.
• Symmetric Difference (setA ^ setB): Elements in either set, but not both.

Practical Code Example

from typing import Set

def audit_user_permissions(granted_roles: Set[str], required_roles: Set[str]) -> None:
    print(f"Granted Roles: {granted_roles}")
    print(f"Required Roles: {required_roles}")

    # Set Intersection
    matching_roles = granted_roles & required_roles
    print(f"Matching Active Roles: {matching_roles}")

    # Set Difference (Missing Permissions)
    missing_roles = required_roles - granted_roles
    if missing_roles:
        print(f"Access Denied! Missing required roles: {missing_roles}")
    else:
        print("Access Granted! All required roles present.")

if __name__ == "__main__":
    current_user_roles: Set[str] = {"read", "write", "comment"}
    admin_requirements: Set[str] = {"read", "write", "deploy", "admin"}
    
    audit_user_permissions(current_user_roles, admin_requirements)
    
    # Fast Deduplication
    raw_tags = ["python", "django", "python", "fastapi", "django"]
    unique_tags = list(set(raw_tags))
    print("Deduplicated Tags:", unique_tags)

Best Practices & Gotchas

• Elements Must Be Hashable: You cannot store mutable containers (like lists or dicts) inside a set. Use frozenset if an immutable set is needed.
• Set Instantiation: Use set() to create an empty set. Writing {} creates an empty dictionary dict!
• Use Set Membership for Fast Lookups: Checking x in my_set runs in $O(1)$ constant time, whereas x in my_list runs in $O(N)$ linear time.

Self-Check Challenge

Write a function find_common_elements(list1: list, list2: list) -> list that uses set intersection to return a list of unique elements present in both inputs.