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()