optimal_pairing.py

from typing import Dict, List, Tuple
from dataclasses import dataclass
import statistics
import math

# Type definitions
Person = str
Satisfaction = float
Pairing = Tuple[Person, Person]
PairingScheme = List[Pairing]
PreferenceLists = Dict[Person, List[Person]]
Preferences = Dict[Person, Dict[Person, Satisfaction]]

@dataclass
class PairingResult:
    """Class to store the result of a pairing scheme evaluation."""
    pairing_scheme: PairingScheme
    min_satisfaction: float
    avg_satisfaction: float
    individual_satisfaction: Dict[Person, float]

def compute_preferences_from_lists(preference_lists: PreferenceLists, people: List[Person]) -> Preferences:
    """
    Compute normalized preference values from preference lists.
    For a list of length n, the highest preference is 1.0 and the lowest is 1/n.
    If a person is not in the preference list, they get the lowest possible score.
    """
    preferences: Preferences = {}

    for person in people:
        preferences[person] = {}
        pref_list = preference_lists.get(person, [])

        # Process people in the preference list
        if pref_list:
            list_length = len(pref_list)

            for position, partner in enumerate(pref_list):
                # Calculate preference value: starts at 1.0, decreases linearly to 1/list_length
                preference_value = 1.0 - (position / list_length) * (1.0 - 1.0/list_length)
                preferences[person][partner] = preference_value

        # Assign lowest score to anyone not in the preference list
        lowest_score = 1.0/len(people) if pref_list else 0.0
        for partner in people:
            if partner != person and partner not in preferences[person]:
                preferences[person][partner] = lowest_score

    return preferences

def validate_preference_lists(preference_lists: PreferenceLists, people: List[Person]) -> None:
    """Validate preference lists to ensure they don't contain duplicates or invalid people."""
    all_people_set = set(people)

    for person, pref_list in preference_lists.items():
        # Check if the person is valid
        if person not in all_people_set:
            raise ValueError(f"Person '{person}' in preference lists is not in the people list")

        # Check for duplicates in preference list
        if len(pref_list) != len(set(pref_list)):
            raise ValueError(f"Duplicate entries in preference list for '{person}'")

        # Check if all entries in preference list are valid
        for preferred_person in pref_list:
            if preferred_person not in all_people_set:
                raise ValueError(f"Unknown person '{preferred_person}' in preference list for '{person}'")

            # Make sure person doesn't prefer themselves
            if preferred_person == person:
                raise ValueError(f"Person '{person}' lists themselves in their preference list")

def generate_all_pairings(people: List[Person]) -> List[PairingScheme]:
    """Generate all possible ways to pair the given people."""
    if len(people) % 2 != 0:
        raise ValueError("Number of people must be even")

    # Helper function to generate all possible pairings recursively
    def generate_pairings_helper(remaining_people: List[Person]) -> List[PairingScheme]:
        if not remaining_people:
            return [[]]

        person = remaining_people[0]
        new_remaining = remaining_people[1:]
        result: List[PairingScheme] = []

        for i in range(len(new_remaining)):
            partner = new_remaining[i]
            pairing = (person, partner) if person < partner else (partner, person)

            # Generate all pairings for the remaining people
            sub_pairings = generate_pairings_helper(new_remaining[:i] + new_remaining[i+1:])

            # Add the current pairing to each sub-pairing
            for sub_pairing in sub_pairings:
                result.append([pairing] + sub_pairing)

        return result

    result = generate_pairings_helper(people)

    # Assert that the number of pairings matches the mathematical formula
    assert len(result) == calculate_expected_pairing_count(len(people)), "Pairing count mismatch"

    return result

def evaluate_pairing_scheme(
    pairing_scheme: PairingScheme,
    preferences: Preferences
) -> PairingResult:
    """Evaluate a pairing scheme based on satisfaction scores."""
    individual_satisfaction: Dict[Person, float] = {}

    # Calculate each person's satisfaction
    for pair in pairing_scheme:
        person1, person2 = pair

        # Check if the preferences exist, otherwise set to 0 (no preference)
        satisfaction1 = preferences.get(person1, {}).get(person2, 0.0)
        satisfaction2 = preferences.get(person2, {}).get(person1, 0.0)

        individual_satisfaction[person1] = satisfaction1
        individual_satisfaction[person2] = satisfaction2

    # Calculate metrics
    min_satisfaction = min(individual_satisfaction.values())
    avg_satisfaction = statistics.mean(individual_satisfaction.values())

    return PairingResult(
        pairing_scheme=pairing_scheme,
        min_satisfaction=min_satisfaction,
        avg_satisfaction=avg_satisfaction,
        individual_satisfaction=individual_satisfaction
    )

def find_optimal_pairing(
    people: List[Person],
    preference_lists: PreferenceLists
) -> PairingResult:
    """
    Find the optimal pairing of people based on preference lists.
    Optimize first for the minimum satisfaction, then for the average satisfaction.
    Handles incomplete preference lists by assigning the lowest score to unlisted people.
    """

    # Validate preference lists
    validate_preference_lists(preference_lists, people)

    # Compute preferences from the preference lists
    preferences = compute_preferences_from_lists(preference_lists, people)

    all_pairing_schemes = generate_all_pairings(people)
    evaluated_schemes = [evaluate_pairing_scheme(scheme, preferences) for scheme in all_pairing_schemes]

    # Sort by minimum satisfaction (descending), then by average satisfaction (descending)
    evaluated_schemes.sort(
        key=lambda result: (result.min_satisfaction*0.8+result.avg_satisfaction*0.2),
        reverse=True
    )

    return evaluated_schemes[0]

def print_pairing_results(result: PairingResult) -> None:
    """Print the results of the optimal pairing scheme in a readable format."""
    print("Optimal Pairing Scheme:")
    for pair in result.pairing_scheme:
        person1, person2 = pair
        print(f"  {person1} paired with {person2}")

    print("\nIndividual Satisfaction:")
    for person, satisfaction in sorted(result.individual_satisfaction.items()):
        print(f"  {person}: {satisfaction:.4f}")

    print(f"\nMinimum Satisfaction: {result.min_satisfaction:.4f}")
    print(f"Average Satisfaction: {result.avg_satisfaction:.4f}")

def calculate_expected_pairing_count(n_people: int) -> int:
    """
    Calculate the expected number of possible pairings for n people.
    Formula: (2n)! / (2^n * n!) where n is the number of pairs.
    """
    if n_people % 2 != 0:
        raise ValueError("Number of people must be even")

    n_pairs = n_people // 2
    return math.factorial(n_people) // (2**n_pairs * math.factorial(n_pairs))

# Example usage
def main() -> None:
    # Example preference lists (in order of preference)
    preference_lists: PreferenceLists = {
        "Alice": ["Julia", "Bob", "Frank", "David"],
        "Bob": ["Charlie", "Alice", "Heidi", "Ivan", "Eve", "Frank", "David", "Grace", "Julia"],
        "Charlie": ["Grace", "David", "Bob"],
        "David": ["Eve", "Charlie", "Frank", "Julia", "Grace", "Alice", "Bob", "Ivan", "Heidi"],
        "Eve": ["David", "Ivan", "Julia", "Frank", "Bob", "Heidi"],
        "Frank": ["Heidi", "David", "Alice", "Eve", "Julia", "Charlie", "Bob", "Ivan", "Grace"],
        "Grace": ["Charlie", "Ivan", "Heidi", "Julia", "David", "Bob", "Alice", "Frank", "Eve"],
        "Heidi": ["Frank", "Bob", "Grace"],
        "Ivan": ["Eve", "Grace", "Bob", "Julia", "Heidi", "Charlie", "Frank", "David", "Alice"],
        "Julia": ["Alice", "Heidi", "Ivan", "Charlie", "David", "Eve", "Frank", "Bob", "Grace"]
    }

    people = list(preference_lists.keys())

    print(f"We will evaluate {calculate_expected_pairing_count(len(people))} possible pairings.")

    optimal_result = find_optimal_pairing(people, preference_lists)
    print_pairing_results(optimal_result)

if __name__ == "__main__":
    main()