From 87738b8aac5e22c53772cc6a4447981af4ae09c9 Mon Sep 17 00:00:00 2001 From: Jeff Hemminger Date: Fri, 12 Sep 2025 23:59:40 +0900 Subject: [PATCH] moved modules --- Cargo.toml | 3 + src/algorithms/mod.rs | 7 + .../stable_matching/gale_shapley.rs | 941 ++++++++++++++++++ src/algorithms/stable_matching/mod.rs | 11 + src/lib.rs | 6 + src/main.rs | 941 +----------------- 6 files changed, 976 insertions(+), 933 deletions(-) create mode 100644 src/algorithms/mod.rs create mode 100644 src/algorithms/stable_matching/gale_shapley.rs create mode 100644 src/algorithms/stable_matching/mod.rs create mode 100644 src/lib.rs diff --git a/Cargo.toml b/Cargo.toml index c62b0b4..7ca51a7 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -5,3 +5,6 @@ edition = "2024" [dependencies] rand = "0.8" + +[lib] +doctest = false diff --git a/src/algorithms/mod.rs b/src/algorithms/mod.rs new file mode 100644 index 0000000..8b1fb91 --- /dev/null +++ b/src/algorithms/mod.rs @@ -0,0 +1,7 @@ +//! Core algorithm implementations organized by problem type. + +pub mod stable_matching; + +// Re-export all algorithm modules for easier access +pub use stable_matching::*; + diff --git a/src/algorithms/stable_matching/gale_shapley.rs b/src/algorithms/stable_matching/gale_shapley.rs new file mode 100644 index 0000000..5d49ce4 --- /dev/null +++ b/src/algorithms/stable_matching/gale_shapley.rs @@ -0,0 +1,941 @@ +//! # Gale-Shapley Stable Matching Algorithm +//! +//! This crate implements the Gale-Shapley algorithm for solving the stable matching problem +//! using functional programming principles inspired by category theory and type theory. +//! +//! The implementation features: +//! - Type-safe preference handling with validation +//! - Monadic state management for algorithm execution +//! - Pure functional composition where possible +//! - Comprehensive error handling with `Result` types +//! +//! ## Example +//! +//! ``` +//! use std::collections::HashMap; +//! use algorithms::stable_matching::*; +//! +//! // Generate a random instance and solve it +//! let problem = generate_random_instance(3)?; +//! let solution = solve_stable_matching(problem); +//! +//! // All men should be matched +//! assert_eq!(solution.free_men.len(), 0); +//! # Ok::<(), &'static str>(()) +//! ``` + +use std::collections::{HashMap, HashSet}; +use rand::seq::SliceRandom; + +/// Represents the gender of a person in the matching problem. +/// +/// This enum is used to distinguish between the two sides of the bipartite matching. +/// In the classical formulation, these are typically "men" and "women", but the +/// algorithm applies to any two-sided matching scenario. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum Gender { + Male, + Female, +} + +/// A person participating in the stable matching problem. +/// +/// Each person has a unique identifier and belongs to one of two groups +/// distinguished by gender. The algorithm ensures each person from one +/// group is matched with exactly one person from the other group. +/// +/// ## Type Theory Note +/// This represents an element in one of two disjoint sets that form +/// the domain of our matching function. +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct Person { + pub id: u32, + pub gender: Gender, +} + +/// Represents a person's ordered preference list over potential partners. +/// +/// This structure encapsulates the total ordering required by the Gale-Shapley +/// algorithm. Each person must have a complete, strict preference ordering +/// over all potential partners. +/// +/// ## Category Theory Note +/// This represents a morphism in the category of preferences, where objects +/// are people and morphisms represent preference relations. +/// +/// ## Examples +/// +/// ``` +/// # use algorithms::stable_matching::*; +/// // Person 1 prefers partners in order: 3, 1, 2 +/// let prefs = Preferences::new(1, vec!)?;[1][2][3] +/// +/// // Check if person 3 is preferred over person 2 +/// assert!(prefs.prefers(3, 2)?); +/// # Ok::<(), &'static str>(()) +/// ``` +#[derive(Debug, Clone)] +pub struct Preferences { + /// The ordered list of preferred partner IDs (most preferred first) + pub ordered_ids: Vec, + /// The ID of the person who holds these preferences + pub person_id: u32, +} + +impl Preferences { + + /// Creates a new preference list with validation. + /// + /// # Arguments + /// * `person_id` - The ID of the person who holds these preferences + /// * `ordered_ids` - List of preferred partner IDs in order of preference + /// + /// # Returns + /// * `Ok(Preferences)` - Valid preference list + /// * `Err(&'static str)` - Error message if validation fails + /// + /// # Errors + /// * Returns error if the preference list is empty + /// * Returns error if there are duplicate preferences + /// + /// # Examples + /// + /// ``` + /// # use algorithms::stable_matching::*; + /// # use crate::Preferences; + /// // Valid preferences + /// let prefs = Preferences::new(1, vec!)?;[2][3][4] + /// + /// // Invalid - empty list + /// assert!(Preferences::new(1, vec![]).is_err()); + /// + /// // Invalid - duplicates + /// assert!(Preferences::new(1, vec!).is_err());[3][2] + /// # Ok::<(), &'static str>(()) + /// ``` + pub fn new(person_id: u32, ordered_ids: Vec) -> Result { + if ordered_ids.is_empty() { + return Err("Preference list cannot be empty"); + } + + let mut unique_ids = ordered_ids.clone(); + unique_ids.sort(); + unique_ids.dedup(); + if unique_ids.len() != ordered_ids.len() { + return Err("No duplicate preferences allowed"); + } + + Ok(Preferences { + person_id, + ordered_ids, + }) + } + + /// Determines if person `a_id` is preferred over person `b_id`. + /// + /// This implements the strict preference relation required for stable matching. + /// Returns `true` if `a_id` appears earlier in the preference list than `b_id`. + /// + /// # Arguments + /// * `a_id` - ID of the first person to compare + /// * `b_id` - ID of the second person to compare + /// + /// # Returns + /// * `Ok(true)` - If `a_id` is preferred over `b_id` + /// * `Ok(false)` - If `b_id` is preferred over `a_id` + /// * `Err(&'static str)` - If either person is not in the preference list + /// + /// # Mathematical Note + /// This implements the relation `a_id ≻ b_id` in preference theory notation. + /// + /// # Examples + /// + /// ``` + /// # use algorithms::stable_matching::*; + /// # use crate::Preferences; + /// let prefs = Preferences::new(1, vec!)?;[2][3][5] + /// + /// assert!(prefs.prefers(3, 5)?); // 3 is preferred over 5 + /// assert!(!prefs.prefers(5, 3)?); // 5 is not preferred over 3 + /// # Ok::<(), &'static str>(()) + /// ``` + pub fn prefers(&self, a_id: u32, b_id: u32) -> Result { + let pos_a = self.ordered_ids.iter().position(|&id| id == a_id) + .ok_or("Person A not found in preference list")?; + let pos_b = self.ordered_ids.iter().position(|&id| id == b_id) + .ok_or("Person B not found in preference list")?; + + Ok(pos_a < pos_b) + } + + /// Returns the most preferred person's ID. + /// + /// # Returns + /// The ID of the person at the top of this preference list. + /// + /// # Panics + /// Panics if the preference list is empty (which should be impossible + /// if constructed through `new()`). + /// + /// # Examples + /// + /// ``` + /// # use algorithms::stable_matching::*; + /// # use crate::Preferences; + /// use algorithms::stable_matching::*; + /// let prefs = Preferences::new(1, vec!)?;[7][3][5] + /// assert_eq!(prefs.most_preferred(), 7); + /// # Ok::<(), &'static str>(()) + /// ``` + pub fn most_preferred(&self) -> u32 { + self.ordered_ids[0] + } +} + +/// The main structure representing a stable matching problem instance. +/// +/// This contains both the problem specification (people and their preferences) +/// and the mutable algorithm state (current engagements, proposal history, etc.). +/// +/// The structure follows functional programming principles by clearly separating +/// immutable problem data from mutable algorithm state. +/// +/// ## Algorithm State +/// The Gale-Shapley algorithm maintains several pieces of state: +/// - Current engagements between people +/// - History of proposals made by each person +/// - Set of currently unmatched people +/// +/// ## Type Safety +/// All operations on this structure return `Result` types to handle +/// error conditions gracefully without panics. +#[derive(Debug,Clone)] +pub struct StableMatchingProblem { + /// All male participants in the matching + pub men: Vec, + /// All female participants in the matching + pub women: Vec, + /// Preference lists for all participants, indexed by person ID + pub preferences: HashMap, + // Mutable algorithm state + /// Current engagements: woman_id -> man_id + pub engagements: HashMap, + /// Proposal history: man_id -> Set of women proposed to + pub proposal_history: HashMap>, + /// Set of currently unmatched men + pub free_men: HashSet, +} + +impl StableMatchingProblem { + /// Creates a new stable matching problem instance with validation. + /// + /// # Arguments + /// * `men` - Vector of male participants + /// * `women` - Vector of female participants + /// * `preferences` - HashMap of preference lists for all participants + /// + /// # Returns + /// * `Ok(StableMatchingProblem)` - Valid problem instance + /// * `Err(&'static str)` - Error message if validation fails + /// + /// # Errors + /// * Returns error if any man doesn't have Male gender + /// * Returns error if any woman doesn't have Female gender + /// * Returns error if the number of men and women are not equal + /// + /// # Examples + /// + /// ``` + /// # use algorithms::stable_matching::*; + /// # use std::collections::HashMap; + /// # use crate::{Person, Gender, Preferences, StableMatchingProblem}; + /// let men = vec![Person { id: 1, gender: Gender::Male }]; + /// let women = vec![Person { id: 2, gender: Gender::Female }]; + /// let mut prefs = HashMap::new(); + /// prefs.insert(1, Preferences::new(1, vec!)?);[11] + /// prefs.insert(2, Preferences::new(2, vec!)?);[12] + /// + /// let problem = StableMatchingProblem::new(men, women, prefs)?; + /// assert_eq!(problem.free_men.len(), 1); + /// # Ok::<(), &'static str>(()) + /// ``` + pub fn new( + men: Vec, + women: Vec, + preferences: HashMap, + ) -> Result { + // Validation + if men.iter().any(|p| p.gender != Gender::Male) { + return Err("All men must have Male gender"); + } + if women.iter().any(|p| p.gender != Gender::Female) { + return Err("All women must have Female gender"); + } + if men.len() != women.len() { + return Err("Must have equal numbers of men and women"); + } + + // Initialize mutable state + let mut free_men = HashSet::new(); + let mut proposal_history = HashMap::new(); + + for man in &men { + free_men.insert(man.id); + proposal_history.insert(man.id, HashSet::new()); + } + + Ok(StableMatchingProblem { + men, + women, + preferences, + engagements: HashMap::new(), + proposal_history, + free_men, + }) + } + + /// Retrieves preference list for a given person. + /// + /// # Arguments + /// * `person_id` - The ID of the person whose preferences to retrieve + /// + /// # Returns + /// * `Ok(&Preferences)` - Reference to the person's preferences + /// * `Err(&'static str)` - Error if no preferences found for this person + pub fn get_preferences(&self, person_id: u32) -> Result<&Preferences, &'static str> { + self.preferences.get(&person_id) + .ok_or("No preferences found for person") + } + + /// Checks if a woman is currently unengaged. + /// + /// # Arguments + /// * `woman_id` - The ID of the woman to check + /// + /// # Returns + /// `true` if the woman is free, `false` if she is engaged + pub fn is_woman_free(&self, woman_id: u32) -> bool { + !self.engagements.contains_key(&woman_id) + } + + /// Checks if a man is currently unengaged. + /// + /// # Arguments + /// * `man_id` - The ID of the man to check + /// + /// # Returns + /// `true` if the man is free, `false` if he is engaged + pub fn is_man_free(&self, man_id: u32) -> bool { + self.free_men.contains(&man_id) + } + + /// Gets the ID of the man currently engaged to a woman. + /// + /// # Arguments + /// * `woman_id` - The ID of the woman + /// + /// # Returns + /// * `Some(man_id)` - If the woman is engaged + /// * `None` - If the woman is free + pub fn get_engaged_man(&self, woman_id: u32) -> Option { + self.engagements.get(&woman_id).copied() + } + + /// Creates an engagement between a man and woman, breaking any existing engagement. + /// + /// This operation maintains the invariant that each woman is engaged to at most + /// one man, and each man is engaged to at most one woman. + /// + /// # Arguments + /// * `man_id` - The ID of the man to engage + /// * `woman_id` - The ID of the woman to engage + /// + /// # Side Effects + /// * If the woman was previously engaged, her former partner becomes free + /// * The man is removed from the free men set + /// * The engagement is recorded in the engagements map + pub fn engage(&mut self, man_id: u32, woman_id: u32) { + // Break existing engagement if any + if let Some(current_man) = self.engagements.get(&woman_id) { + self.free_men.insert(*current_man); + } + + // Create new engagement + self.engagements.insert(woman_id, man_id); + self.free_men.remove(&man_id); + } + + /// Checks if a man has already proposed to a specific woman. + /// + /// # Arguments + /// * `man_id` - The ID of the man + /// * `woman_id` - The ID of the woman + /// + /// # Returns + /// `true` if the man has previously proposed to this woman + pub fn has_proposed_to(&self, man_id: u32, woman_id: u32) -> bool { + self.proposal_history + .get(&man_id) + .map_or(false, |set| set.contains(&woman_id)) + } + + /// Records that a man has proposed to a woman. + /// + /// # Arguments + /// * `man_id` - The ID of the man making the proposal + /// * `woman_id` - The ID of the woman receiving the proposal + pub fn record_proposal(&mut self, man_id: u32, woman_id: u32) { + self.proposal_history + .entry(man_id) + .or_insert_with(HashSet::new) + .insert(woman_id); + } + + /// Checks if a man has proposed to all possible partners. + /// + /// # Arguments + /// * `man_id` - The ID of the man to check + /// + /// # Returns + /// `true` if the man has exhausted all possible proposals + pub fn has_proposed_to_all(&self, man_id: u32) -> bool { + self.proposal_history + .get(&man_id) + .map_or(false, |set| set.len() == self.women.len()) + } + + /// Finds the next woman this man should propose to according to his preferences. + /// + /// Returns the highest-ranked woman in his preference list to whom he + /// has not yet proposed. + /// + /// # Arguments + /// * `man_id` - The ID of the man + /// + /// # Returns + /// * `Ok(Some(woman_id))` - The next woman to propose to + /// * `Ok(None)` - If he has proposed to everyone + /// * `Err(&'static str)` - If preferences not found for this man + pub fn next_woman_to_propose(&self, man_id: u32) -> Result, &'static str> { + let prefs = self.get_preferences(man_id)?; + let proposed_set = self.proposal_history.get(&man_id).unwrap(); + + Ok(prefs.ordered_ids + .iter() + .find(|&&woman_id| !proposed_set.contains(&woman_id)) + .copied()) + } +} + +/// A State monad implementation for managing algorithm state transformations. +/// +/// This follows category theory principles by encapsulating stateful computations +/// in a composable, purely functional way. The State monad allows us to thread +/// mutable state through a series of computations while maintaining referential +/// transparency at the functional level. +/// +/// ## Category Theory Background +/// The State monad is defined as `State s a = s -> (a, s)`, representing +/// a function that takes an initial state and returns a value along with +/// a new state. This forms a monad with the following operations: +/// - `return`: Creates a state computation that returns a value without changing state +/// - `bind` (>>=): Composes state computations sequentially +/// +/// ## Type Parameters +/// * `S` - The type of the state being threaded through computations +/// * `A` - The type of the value produced by the computation +pub struct State { + run: Box (A, S)>, +} + +impl State { + + /// Creates a new state computation from a function. + /// + /// This is the fundamental constructor for the State monad. + /// + /// # Arguments + /// * `f` - A function that takes initial state and returns (value, new_state) + /// + /// # Examples + /// + /// ``` + /// # use algorithms::stable_matching::*; + /// // A state computation that increments a counter and returns the old value + /// let increment = State::new(|count: i32| (count, count + 1)); + /// let (old_value, new_count) = increment.run_state(5); + /// assert_eq!(old_value, 5); + /// assert_eq!(new_count, 6); + /// ``` + pub fn new(f: F) -> Self + where F: FnOnce(S) -> (A, S) + 'static { + State { run: Box::new(f) } + } + + /// Maps a function over the value produced by a state computation. + /// + /// This implements the Functor instance for State, allowing transformation + /// of the computed value without affecting the state threading. + /// + /// # Type Parameters + /// * `B` - The type of the transformed value + /// * `F` - The transformation function type + /// + /// # Arguments + /// * `f` - Function to transform the computed value + /// + /// # Category Theory Note + /// This satisfies the functor laws: + /// - `fmap id = id` + /// - `fmap (g . f) = fmap g . fmap f` + pub fn map B + 'static>(self, f: F) -> State { + State::new(move |s| { + let (a, s1) = (self.run)(s); + (f(a), s1) + }) + } + + /// Sequentially composes two state computations. + /// + /// This implements the monadic bind operation (>>=), enabling sequential + /// composition of stateful computations where the result of the first + /// computation can influence the second. + /// + /// # Type Parameters + /// * `B` - The type of value produced by the second computation + /// * `F` - The function that creates the second computation + /// + /// # Arguments + /// * `f` - Function that takes the first result and produces a new state computation + /// + /// # Monad Laws + /// This satisfies the monad laws: + /// - Left identity: `return a >>= f ≡ f a` + /// - Right identity: `m >>= return ≡ m` + /// - Associativity: `(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)` + pub fn flat_map State + 'static>(self, f: F) -> State { + State::new(move |s| { + let (a, s1) = (self.run)(s); + (f(a).run)(s1) + }) + } + + /// Executes the state computation with an initial state. + /// + /// This "runs" the state monad computation, providing the initial state + /// and extracting both the computed value and final state. + /// + /// # Arguments + /// * `initial_state` - The starting state for the computation + /// + /// # Returns + /// A tuple of (computed_value, final_state) + pub fn run_state(self, initial_state: S) -> (A, S) { + (self.run)(initial_state) + } +} + +/// Pure function to get the next free man from the problem state. +/// +/// Following functional programming principles, this function has no side effects +/// and always returns the same output for the same input. +/// +/// # Arguments +/// * `state` - Current problem state +/// +/// # Returns +/// * `Some(man_id)` - ID of a free man, if any exist +/// * `None` - If all men are engaged +fn get_next_free_man(state: &StableMatchingProblem) -> Option { + state.free_men.iter().copied().next() +} + +/// Pure function to find the next woman a man should propose to. +/// +/// This implements the core logic of the Gale-Shapley algorithm: each man +/// proposes to women in order of his preference, skipping those he has +/// already proposed to. +/// +/// # Arguments +/// * `state` - Current problem state +/// * `man_id` - ID of the man making proposals +/// +/// # Returns +/// * `Some(woman_id)` - Next woman to propose to +/// * `None` - If he has proposed to all women +fn find_next_proposal_target(state: &StableMatchingProblem, man_id: u32) -> Option { + state.preferences.get(&man_id) + .and_then(|prefs| { + let proposed_set = state.proposal_history.get(&man_id)?; + prefs.ordered_ids + .iter() + .find(|&&woman_id| !proposed_set.contains(&woman_id)) + .copied() + }) +} + +/// Pure function to determine if a woman prefers a new man over her current partner. +/// +/// This implements the stability condition check: a woman will switch partners +/// if she prefers the new proposer over her current partner. +/// +/// # Arguments +/// * `state` - Current problem state +/// * `woman_id` - ID of the woman making the choice +/// * `new_man_id` - ID of the new proposer +/// * `current_man_id` - ID of her current partner +/// +/// # Returns +/// `true` if the woman prefers the new man, `false` otherwise +/// +/// # Stability Theory +/// This function implements the core stability check. A matching is stable +/// if no woman would prefer to switch from her current partner to any man +/// who would also prefer to switch to her. +fn woman_prefers_new_man(state: &StableMatchingProblem, woman_id: u32, new_man_id: u32, current_man_id: u32) -> bool { + state.preferences.get(&woman_id) + .map(|woman_prefs| { + let new_pos = woman_prefs.ordered_ids.iter().position(|&id| id == new_man_id); + let current_pos = woman_prefs.ordered_ids.iter().position(|&id| id == current_man_id); + + match (new_pos, current_pos) { + (Some(new_p), Some(current_p)) => new_p < current_p, + _ => false, + } + }) + .unwrap_or(false) +} + +/// Creates a single state transition for the Gale-Shapley algorithm. +/// +/// This function encapsulates one iteration of the algorithm: +/// 1. Find a free man +/// 2. Find his next preferred woman to propose to +/// 3. Handle the proposal (engage, reject, or switch partners) +/// +/// The function is pure in the sense that it returns a state computation +/// rather than directly mutating state. +/// +/// # Returns +/// A State monad computation that performs one algorithm step +/// +/// # Algorithm Correctness +/// Each step maintains the algorithm invariants: +/// - Each woman is engaged to at most one man +/// - Men propose in preference order +/// - Women always accept better proposals +fn update_state() -> State { + State::new(|mut state: StableMatchingProblem| { + if let Some(man_id) = get_next_free_man(&state) { + if let Some(woman_id) = find_next_proposal_target(&state, man_id) { + // Record the proposal + state.proposal_history.get_mut(&man_id).unwrap().insert(woman_id); + + match state.engagements.get(&woman_id) { + None => { + // Woman is free, engage + state.engagements.insert(woman_id, man_id); + state.free_men.remove(&man_id); + } + Some(¤t_man_id) => { + // Check if woman prefers new man + if woman_prefers_new_man(&state, woman_id, man_id, current_man_id) { + // Switch engagements + state.engagements.insert(woman_id, man_id); + state.free_men.remove(&man_id); + state.free_men.insert(current_man_id); + } + // Otherwise, man remains free + } + } + } + } + ((), state) + }) +} + +/// Solves the stable matching problem using functional composition. +/// +/// This function repeatedly applies the state transformation until no free men remain, +/// implementing the complete Gale-Shapley algorithm through monadic composition. +/// +/// # Arguments +/// * `problem` - Initial problem instance with all men free +/// +/// # Returns +/// The solved problem with all participants matched +/// +/// # Algorithm Properties +/// The Gale-Shapley algorithm guarantees: +/// - **Termination**: The algorithm always terminates in O(n²) proposals +/// - **Stability**: The resulting matching is stable (no blocking pairs) +/// - **Optimality**: The matching is man-optimal and woman-pessimal +/// +/// # Examples +/// +/// ``` +/// # use algorithms::stable_matching::*; +/// let problem = generate_random_instance(4)?; +/// let solution = solve_stable_matching(problem); +/// +/// // Verify all men are matched +/// assert_eq!(solution.free_men.len(), 0); +/// assert_eq!(solution.engagements.len(), 4); +/// # Ok::<(), &'static str>(()) +/// ``` +//pub fn solve_stable_matching(mut problem: StableMatchingProblem) -> StableMatchingProblem { +// while !problem.free_men.is_empty() { +// let (_, new_state) = update_state().run_state(problem); +// problem = new_state; +// } +// problem +//} + +/// Solves the stable matching problem using functional unfold composition. +/// +/// This implementation uses `std::iter::successors` to express the algorithm +/// as an unfold (anamorphism) - generating successive problem states from +/// the initial configuration until convergence to a stable matching. +/// +/// # Arguments +/// * `problem` - Initial problem instance with all men free +/// +/// # Returns +/// The solved problem with all participants matched +/// +/// # Algorithm Complexity +/// - Time: O(n²) in worst case +/// - Space: O(n) for state representation +/// +/// # Functional Programming Note +/// This demonstrates the unfold pattern - the categorical dual of fold. +/// While fold consumes structure to produce values, unfold generates +/// structure from an initial seed value. +/// +/// # Examples +/// +/// ``` +/// # use algorithms::stable_matching::*; +/// let problem = generate_random_instance(4)?; +/// let solution = solve_stable_matching(problem); +/// +/// assert_eq!(solution.free_men.len(), 0); +/// assert_eq!(solution.engagements.len(), 4); +/// # Ok::<(), &'static str>(()) +/// ``` +pub fn solve_stable_matching(problem: StableMatchingProblem) -> StableMatchingProblem { + std::iter::successors(Some(problem), |current_problem| { + if current_problem.free_men.is_empty() { + None // Algorithm has converged - no more states to generate + } else { + // Generate next state using monadic state transformation + let (_, next_state) = update_state().run_state(current_problem.clone()); + Some(next_state) + } + }) + .last() // Extract the final converged state + .expect("Iterator should always yield at least the initial state") +} + +/// Generates a random stable matching problem instance for testing and experimentation. +/// +/// This function creates a problem with the specified number of men and women, +/// where each person has a random preference ordering over all potential partners. +/// +/// # Arguments +/// * `count` - Number of men and women to create (total 2×count participants) +/// +/// # Returns +/// * `Ok(StableMatchingProblem)` - Random problem instance ready to solve +/// * `Err(&'static str)` - Error if problem creation fails +/// +/// # Randomization +/// Uses Fisher-Yates shuffle to create uniformly random preference orderings, +/// ensuring each possible preference profile has equal probability. +/// +/// # Examples +/// +/// ``` +/// # use algorithms::stable_matching::*; +/// // Create a problem with 5 men and 5 women +/// let problem = generate_random_instance(5)?; +/// +/// assert_eq!(problem.men.len(), 5); +/// assert_eq!(problem.women.len(), 5); +/// assert_eq!(problem.preferences.len(), 10); // 5 + 5 +/// # Ok::<(), &'static str>(()) +/// ``` +/// +/// # Use Cases +/// - **Testing**: Generate test cases for algorithm verification +/// - **Benchmarking**: Create instances for performance analysis +/// - **Research**: Study algorithm behavior on random instances +pub fn generate_random_instance(count: usize) -> Result { + let mut rng = rand::thread_rng(); + + // Create people using functional combinators + let men: Vec = (1..=count as u32) + .map(|id| Person { id, gender: Gender::Male }) + .collect(); + + let women: Vec = (1..=count as u32) + .map(|id| Person { id, gender: Gender::Female }) + .collect(); + + let mut preferences = HashMap::new(); + + // Generate men's preferences functionally + for man in &men { + let mut women_ids: Vec = (1..=count as u32).collect(); + women_ids.shuffle(&mut rng); + + let prefs = Preferences::new(man.id, women_ids)?; + preferences.insert(man.id, prefs); + } + + // Generate women's preferences functionally + for woman in &women { + let mut men_ids: Vec = (1..=count as u32).collect(); + men_ids.shuffle(&mut rng); + + let prefs = Preferences::new(woman.id, men_ids)?; + preferences.insert(woman.id, prefs); + } + + StableMatchingProblem::new(men, women, preferences) +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_preferences_creation() { + let prefs = Preferences::new(1, vec![2, 3, 4]).unwrap(); + assert_eq!(prefs.most_preferred(), 2); + assert!(prefs.prefers(2, 3).unwrap()); + assert!(!prefs.prefers(4, 2).unwrap()); + } + + #[test] + fn test_problem_creation() { + let men = vec![ + Person { id: 1, gender: Gender::Male }, + Person { id: 2, gender: Gender::Male }, + ]; + let women = vec![ + Person { id: 1, gender: Gender::Female }, + Person { id: 2, gender: Gender::Female }, + ]; + + let mut preferences = HashMap::new(); + preferences.insert(1, Preferences::new(1, vec![1, 2]).unwrap()); // Man 1 prefs + preferences.insert(2, Preferences::new(2, vec![2, 1]).unwrap()); // Man 2 prefs + + let problem = StableMatchingProblem::new(men, women, preferences).unwrap(); + assert_eq!(problem.free_men.len(), 2); + } + + #[test] + fn test_generate_random_instance() { + // Generate a small test instance (e.g., 4 men and 4 women) + let n = 4; + let result = generate_random_instance(n); + + assert!( + result.is_ok(), + "generate_random_instance returned an error: {:?}", + result.err() + ); + + let instance = result.unwrap(); + + // Check men and women count + assert_eq!(instance.men.len(), n, "Incorrect number of men generated [attached_file:1]"); + assert_eq!(instance.women.len(), n, "Incorrect number of women generated [attached_file:1]"); + + // Check that preferences exist for each man and woman + for man in &instance.men { + assert!( + instance.preferences.contains_key(&man.id), + "Preference list missing for man {} [attached_file:1]", + man.id + ); + let prefs = instance.preferences.get(&man.id).unwrap(); + // Preferences should list all women without duplicates + assert_eq!( + prefs.ordered_ids.len(), + n, + "Man {} preferences should have length {} [attached_file:1]", + man.id, + n + ); + let mut sorted = prefs.ordered_ids.clone(); + sorted.sort(); + sorted.dedup(); + assert_eq!( + sorted.len(), + n, + "Man {} preferences contain duplicates [attached_file:1]", + man.id + ); + } + + for woman in &instance.women { + assert!( + instance.preferences.contains_key(&woman.id), + "Preference list missing for woman {} [attached_file:1]", + woman.id + ); + let prefs = instance.preferences.get(&woman.id).unwrap(); + assert_eq!( + prefs.ordered_ids.len(), + n, + "Woman {} preferences should have length {} [attached_file:1]", + woman.id, + n + ); + let mut sorted = prefs.ordered_ids.clone(); + sorted.sort(); + sorted.dedup(); + assert_eq!( + sorted.len(), + n, + "Woman {} preferences contain duplicates [attached_file:1]", + woman.id + ); + } + + // Ensure free_men are all the men + for man in &instance.men { + assert!( + instance.free_men.contains(&man.id), + "Man {} should be free initially [attached_file:1]", + man.id + ); + } + + // Ensure proposal_history is initialized for all men and is empty + for man in &instance.men { + let history = instance.proposal_history.get(&man.id).unwrap(); + assert!( + history.is_empty(), + "Proposal history for man {} should be empty [attached_file:1]", + man.id + ); + } + } + + /// Test that demonstrates the documented API usage + #[test] + fn test_basic_functionality() -> Result<(), &'static str> { + let problem = generate_random_instance(3)?; + let solution = solve_stable_matching(problem); + + // All men should be matched + assert_eq!(solution.free_men.len(), 0); + assert_eq!(solution.engagements.len(), 3); + + Ok(()) + } +} diff --git a/src/algorithms/stable_matching/mod.rs b/src/algorithms/stable_matching/mod.rs new file mode 100644 index 0000000..37f5b56 --- /dev/null +++ b/src/algorithms/stable_matching/mod.rs @@ -0,0 +1,11 @@ +//! # Stable Matching Problem +//! +//! Implementation of the Gale-Shapley algorithm for the Stable Matching Problem. + +// Declare submodules if you split them +pub mod gale_shapley; +//pub mod types; + +// Re-export the public API from submodules +pub use gale_shapley::*; +//pub use types::*; diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..de789ac --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,6 @@ +pub mod algorithms; +//pub mod common; + +// Re-export commonly used items +pub use algorithms::*; +//pub use common::types::*; diff --git a/src/main.rs b/src/main.rs index 4d6a0bf..56547ee 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,936 +1,11 @@ -//! # Gale-Shapley Stable Matching Algorithm -//! -//! This crate implements the Gale-Shapley algorithm for solving the stable matching problem -//! using functional programming principles inspired by category theory and type theory. -//! -//! The implementation features: -//! - Type-safe preference handling with validation -//! - Monadic state management for algorithm execution -//! - Pure functional composition where possible -//! - Comprehensive error handling with `Result` types -//! -//! ## Example -//! -//! ``` -//! use std::collections::HashMap; -//! -//! // Generate a random instance and solve it -//! let problem = generate_random_instance(3)?; -//! let solution = solve_stable_matching(problem); -//! -//! // All men should be matched -//! assert_eq!(solution.free_men.len(), 0); -//! # Ok::<(), &'static str>(()) -//! ``` +//use algorithms::stable_matching::*; +use algorithms::algorithms::stable_matching::*; -use std::collections::{HashMap, HashSet}; -use rand::seq::SliceRandom; - -/// Represents the gender of a person in the matching problem. -/// -/// This enum is used to distinguish between the two sides of the bipartite matching. -/// In the classical formulation, these are typically "men" and "women", but the -/// algorithm applies to any two-sided matching scenario. -#[derive(Debug, Clone, Copy, PartialEq, Eq)] -pub enum Gender { - Male, - Female, -} - -/// A person participating in the stable matching problem. -/// -/// Each person has a unique identifier and belongs to one of two groups -/// distinguished by gender. The algorithm ensures each person from one -/// group is matched with exactly one person from the other group. -/// -/// ## Type Theory Note -/// This represents an element in one of two disjoint sets that form -/// the domain of our matching function. -#[derive(Debug, Clone, PartialEq, Eq)] -pub struct Person { - pub id: u32, - pub gender: Gender, -} - -/// Represents a person's ordered preference list over potential partners. -/// -/// This structure encapsulates the total ordering required by the Gale-Shapley -/// algorithm. Each person must have a complete, strict preference ordering -/// over all potential partners. -/// -/// ## Category Theory Note -/// This represents a morphism in the category of preferences, where objects -/// are people and morphisms represent preference relations. -/// -/// ## Examples -/// -/// ``` -/// # use crate::Preferences; -/// // Person 1 prefers partners in order: 3, 1, 2 -/// let prefs = Preferences::new(1, vec!)?;[1][2][3] -/// -/// // Check if person 3 is preferred over person 2 -/// assert!(prefs.prefers(3, 2)?); -/// # Ok::<(), &'static str>(()) -/// ``` -#[derive(Debug, Clone)] -pub struct Preferences { - /// The ordered list of preferred partner IDs (most preferred first) - pub ordered_ids: Vec, - /// The ID of the person who holds these preferences - pub person_id: u32, -} - -impl Preferences { - - /// Creates a new preference list with validation. - /// - /// # Arguments - /// * `person_id` - The ID of the person who holds these preferences - /// * `ordered_ids` - List of preferred partner IDs in order of preference - /// - /// # Returns - /// * `Ok(Preferences)` - Valid preference list - /// * `Err(&'static str)` - Error message if validation fails - /// - /// # Errors - /// * Returns error if the preference list is empty - /// * Returns error if there are duplicate preferences - /// - /// # Examples - /// - /// ``` - /// # use crate::Preferences; - /// // Valid preferences - /// let prefs = Preferences::new(1, vec!)?;[2][3][4] - /// - /// // Invalid - empty list - /// assert!(Preferences::new(1, vec![]).is_err()); - /// - /// // Invalid - duplicates - /// assert!(Preferences::new(1, vec!).is_err());[3][2] - /// # Ok::<(), &'static str>(()) - /// ``` - pub fn new(person_id: u32, ordered_ids: Vec) -> Result { - if ordered_ids.is_empty() { - return Err("Preference list cannot be empty"); - } - - let mut unique_ids = ordered_ids.clone(); - unique_ids.sort(); - unique_ids.dedup(); - if unique_ids.len() != ordered_ids.len() { - return Err("No duplicate preferences allowed"); - } - - Ok(Preferences { - person_id, - ordered_ids, - }) - } - - /// Determines if person `a_id` is preferred over person `b_id`. - /// - /// This implements the strict preference relation required for stable matching. - /// Returns `true` if `a_id` appears earlier in the preference list than `b_id`. - /// - /// # Arguments - /// * `a_id` - ID of the first person to compare - /// * `b_id` - ID of the second person to compare - /// - /// # Returns - /// * `Ok(true)` - If `a_id` is preferred over `b_id` - /// * `Ok(false)` - If `b_id` is preferred over `a_id` - /// * `Err(&'static str)` - If either person is not in the preference list - /// - /// # Mathematical Note - /// This implements the relation `a_id ≻ b_id` in preference theory notation. - /// - /// # Examples - /// - /// ``` - /// # use crate::Preferences; - /// let prefs = Preferences::new(1, vec!)?;[2][3][5] - /// - /// assert!(prefs.prefers(3, 5)?); // 3 is preferred over 5 - /// assert!(!prefs.prefers(5, 3)?); // 5 is not preferred over 3 - /// # Ok::<(), &'static str>(()) - /// ``` - pub fn prefers(&self, a_id: u32, b_id: u32) -> Result { - let pos_a = self.ordered_ids.iter().position(|&id| id == a_id) - .ok_or("Person A not found in preference list")?; - let pos_b = self.ordered_ids.iter().position(|&id| id == b_id) - .ok_or("Person B not found in preference list")?; - - Ok(pos_a < pos_b) - } - - /// Returns the most preferred person's ID. - /// - /// # Returns - /// The ID of the person at the top of this preference list. - /// - /// # Panics - /// Panics if the preference list is empty (which should be impossible - /// if constructed through `new()`). - /// - /// # Examples - /// - /// ``` - /// # use crate::Preferences; - /// let prefs = Preferences::new(1, vec!)?;[7][3][5] - /// assert_eq!(prefs.most_preferred(), 7); - /// # Ok::<(), &'static str>(()) - /// ``` - pub fn most_preferred(&self) -> u32 { - self.ordered_ids[0] - } -} - -/// The main structure representing a stable matching problem instance. -/// -/// This contains both the problem specification (people and their preferences) -/// and the mutable algorithm state (current engagements, proposal history, etc.). -/// -/// The structure follows functional programming principles by clearly separating -/// immutable problem data from mutable algorithm state. -/// -/// ## Algorithm State -/// The Gale-Shapley algorithm maintains several pieces of state: -/// - Current engagements between people -/// - History of proposals made by each person -/// - Set of currently unmatched people -/// -/// ## Type Safety -/// All operations on this structure return `Result` types to handle -/// error conditions gracefully without panics. -#[derive(Debug,Clone)] -pub struct StableMatchingProblem { - /// All male participants in the matching - pub men: Vec, - /// All female participants in the matching - pub women: Vec, - /// Preference lists for all participants, indexed by person ID - pub preferences: HashMap, - // Mutable algorithm state - /// Current engagements: woman_id -> man_id - pub engagements: HashMap, - /// Proposal history: man_id -> Set of women proposed to - pub proposal_history: HashMap>, - /// Set of currently unmatched men - pub free_men: HashSet, -} - -impl StableMatchingProblem { - /// Creates a new stable matching problem instance with validation. - /// - /// # Arguments - /// * `men` - Vector of male participants - /// * `women` - Vector of female participants - /// * `preferences` - HashMap of preference lists for all participants - /// - /// # Returns - /// * `Ok(StableMatchingProblem)` - Valid problem instance - /// * `Err(&'static str)` - Error message if validation fails - /// - /// # Errors - /// * Returns error if any man doesn't have Male gender - /// * Returns error if any woman doesn't have Female gender - /// * Returns error if the number of men and women are not equal - /// - /// # Examples - /// - /// ``` - /// # use std::collections::HashMap; - /// # use crate::{Person, Gender, Preferences, StableMatchingProblem}; - /// let men = vec![Person { id: 1, gender: Gender::Male }]; - /// let women = vec![Person { id: 2, gender: Gender::Female }]; - /// let mut prefs = HashMap::new(); - /// prefs.insert(1, Preferences::new(1, vec!)?);[11] - /// prefs.insert(2, Preferences::new(2, vec!)?);[12] - /// - /// let problem = StableMatchingProblem::new(men, women, prefs)?; - /// assert_eq!(problem.free_men.len(), 1); - /// # Ok::<(), &'static str>(()) - /// ``` - pub fn new( - men: Vec, - women: Vec, - preferences: HashMap, - ) -> Result { - // Validation - if men.iter().any(|p| p.gender != Gender::Male) { - return Err("All men must have Male gender"); - } - if women.iter().any(|p| p.gender != Gender::Female) { - return Err("All women must have Female gender"); - } - if men.len() != women.len() { - return Err("Must have equal numbers of men and women"); - } - - // Initialize mutable state - let mut free_men = HashSet::new(); - let mut proposal_history = HashMap::new(); - - for man in &men { - free_men.insert(man.id); - proposal_history.insert(man.id, HashSet::new()); - } - - Ok(StableMatchingProblem { - men, - women, - preferences, - engagements: HashMap::new(), - proposal_history, - free_men, - }) - } - - /// Retrieves preference list for a given person. - /// - /// # Arguments - /// * `person_id` - The ID of the person whose preferences to retrieve - /// - /// # Returns - /// * `Ok(&Preferences)` - Reference to the person's preferences - /// * `Err(&'static str)` - Error if no preferences found for this person - pub fn get_preferences(&self, person_id: u32) -> Result<&Preferences, &'static str> { - self.preferences.get(&person_id) - .ok_or("No preferences found for person") - } +fn main() { + // Example usage of different algorithms + println!("Running algorithm examples..."); - /// Checks if a woman is currently unengaged. - /// - /// # Arguments - /// * `woman_id` - The ID of the woman to check - /// - /// # Returns - /// `true` if the woman is free, `false` if she is engaged - pub fn is_woman_free(&self, woman_id: u32) -> bool { - !self.engagements.contains_key(&woman_id) - } - - /// Checks if a man is currently unengaged. - /// - /// # Arguments - /// * `man_id` - The ID of the man to check - /// - /// # Returns - /// `true` if the man is free, `false` if he is engaged - pub fn is_man_free(&self, man_id: u32) -> bool { - self.free_men.contains(&man_id) - } - - /// Gets the ID of the man currently engaged to a woman. - /// - /// # Arguments - /// * `woman_id` - The ID of the woman - /// - /// # Returns - /// * `Some(man_id)` - If the woman is engaged - /// * `None` - If the woman is free - pub fn get_engaged_man(&self, woman_id: u32) -> Option { - self.engagements.get(&woman_id).copied() - } - - /// Creates an engagement between a man and woman, breaking any existing engagement. - /// - /// This operation maintains the invariant that each woman is engaged to at most - /// one man, and each man is engaged to at most one woman. - /// - /// # Arguments - /// * `man_id` - The ID of the man to engage - /// * `woman_id` - The ID of the woman to engage - /// - /// # Side Effects - /// * If the woman was previously engaged, her former partner becomes free - /// * The man is removed from the free men set - /// * The engagement is recorded in the engagements map - pub fn engage(&mut self, man_id: u32, woman_id: u32) { - // Break existing engagement if any - if let Some(current_man) = self.engagements.get(&woman_id) { - self.free_men.insert(*current_man); - } - - // Create new engagement - self.engagements.insert(woman_id, man_id); - self.free_men.remove(&man_id); - } - - /// Checks if a man has already proposed to a specific woman. - /// - /// # Arguments - /// * `man_id` - The ID of the man - /// * `woman_id` - The ID of the woman - /// - /// # Returns - /// `true` if the man has previously proposed to this woman - pub fn has_proposed_to(&self, man_id: u32, woman_id: u32) -> bool { - self.proposal_history - .get(&man_id) - .map_or(false, |set| set.contains(&woman_id)) - } - - /// Records that a man has proposed to a woman. - /// - /// # Arguments - /// * `man_id` - The ID of the man making the proposal - /// * `woman_id` - The ID of the woman receiving the proposal - pub fn record_proposal(&mut self, man_id: u32, woman_id: u32) { - self.proposal_history - .entry(man_id) - .or_insert_with(HashSet::new) - .insert(woman_id); - } - - /// Checks if a man has proposed to all possible partners. - /// - /// # Arguments - /// * `man_id` - The ID of the man to check - /// - /// # Returns - /// `true` if the man has exhausted all possible proposals - pub fn has_proposed_to_all(&self, man_id: u32) -> bool { - self.proposal_history - .get(&man_id) - .map_or(false, |set| set.len() == self.women.len()) - } - - /// Finds the next woman this man should propose to according to his preferences. - /// - /// Returns the highest-ranked woman in his preference list to whom he - /// has not yet proposed. - /// - /// # Arguments - /// * `man_id` - The ID of the man - /// - /// # Returns - /// * `Ok(Some(woman_id))` - The next woman to propose to - /// * `Ok(None)` - If he has proposed to everyone - /// * `Err(&'static str)` - If preferences not found for this man - pub fn next_woman_to_propose(&self, man_id: u32) -> Result, &'static str> { - let prefs = self.get_preferences(man_id)?; - let proposed_set = self.proposal_history.get(&man_id).unwrap(); - - Ok(prefs.ordered_ids - .iter() - .find(|&&woman_id| !proposed_set.contains(&woman_id)) - .copied()) - } -} - -/// A State monad implementation for managing algorithm state transformations. -/// -/// This follows category theory principles by encapsulating stateful computations -/// in a composable, purely functional way. The State monad allows us to thread -/// mutable state through a series of computations while maintaining referential -/// transparency at the functional level. -/// -/// ## Category Theory Background -/// The State monad is defined as `State s a = s -> (a, s)`, representing -/// a function that takes an initial state and returns a value along with -/// a new state. This forms a monad with the following operations: -/// - `return`: Creates a state computation that returns a value without changing state -/// - `bind` (>>=): Composes state computations sequentially -/// -/// ## Type Parameters -/// * `S` - The type of the state being threaded through computations -/// * `A` - The type of the value produced by the computation -pub struct State { - run: Box (A, S)>, + // Use stable matching + // Use interval scheduling + // etc. } - -impl State { - - /// Creates a new state computation from a function. - /// - /// This is the fundamental constructor for the State monad. - /// - /// # Arguments - /// * `f` - A function that takes initial state and returns (value, new_state) - /// - /// # Examples - /// - /// ``` - /// # use crate::State; - /// // A state computation that increments a counter and returns the old value - /// let increment = State::new(|count: i32| (count, count + 1)); - /// let (old_value, new_count) = increment.run_state(5); - /// assert_eq!(old_value, 5); - /// assert_eq!(new_count, 6); - /// ``` - pub fn new(f: F) -> Self - where F: FnOnce(S) -> (A, S) + 'static { - State { run: Box::new(f) } - } - - /// Maps a function over the value produced by a state computation. - /// - /// This implements the Functor instance for State, allowing transformation - /// of the computed value without affecting the state threading. - /// - /// # Type Parameters - /// * `B` - The type of the transformed value - /// * `F` - The transformation function type - /// - /// # Arguments - /// * `f` - Function to transform the computed value - /// - /// # Category Theory Note - /// This satisfies the functor laws: - /// - `fmap id = id` - /// - `fmap (g . f) = fmap g . fmap f` - pub fn map B + 'static>(self, f: F) -> State { - State::new(move |s| { - let (a, s1) = (self.run)(s); - (f(a), s1) - }) - } - - /// Sequentially composes two state computations. - /// - /// This implements the monadic bind operation (>>=), enabling sequential - /// composition of stateful computations where the result of the first - /// computation can influence the second. - /// - /// # Type Parameters - /// * `B` - The type of value produced by the second computation - /// * `F` - The function that creates the second computation - /// - /// # Arguments - /// * `f` - Function that takes the first result and produces a new state computation - /// - /// # Monad Laws - /// This satisfies the monad laws: - /// - Left identity: `return a >>= f ≡ f a` - /// - Right identity: `m >>= return ≡ m` - /// - Associativity: `(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)` - pub fn flat_map State + 'static>(self, f: F) -> State { - State::new(move |s| { - let (a, s1) = (self.run)(s); - (f(a).run)(s1) - }) - } - - /// Executes the state computation with an initial state. - /// - /// This "runs" the state monad computation, providing the initial state - /// and extracting both the computed value and final state. - /// - /// # Arguments - /// * `initial_state` - The starting state for the computation - /// - /// # Returns - /// A tuple of (computed_value, final_state) - pub fn run_state(self, initial_state: S) -> (A, S) { - (self.run)(initial_state) - } -} - -/// Pure function to get the next free man from the problem state. -/// -/// Following functional programming principles, this function has no side effects -/// and always returns the same output for the same input. -/// -/// # Arguments -/// * `state` - Current problem state -/// -/// # Returns -/// * `Some(man_id)` - ID of a free man, if any exist -/// * `None` - If all men are engaged -fn get_next_free_man(state: &StableMatchingProblem) -> Option { - state.free_men.iter().copied().next() -} - -/// Pure function to find the next woman a man should propose to. -/// -/// This implements the core logic of the Gale-Shapley algorithm: each man -/// proposes to women in order of his preference, skipping those he has -/// already proposed to. -/// -/// # Arguments -/// * `state` - Current problem state -/// * `man_id` - ID of the man making proposals -/// -/// # Returns -/// * `Some(woman_id)` - Next woman to propose to -/// * `None` - If he has proposed to all women -fn find_next_proposal_target(state: &StableMatchingProblem, man_id: u32) -> Option { - state.preferences.get(&man_id) - .and_then(|prefs| { - let proposed_set = state.proposal_history.get(&man_id)?; - prefs.ordered_ids - .iter() - .find(|&&woman_id| !proposed_set.contains(&woman_id)) - .copied() - }) -} - -/// Pure function to determine if a woman prefers a new man over her current partner. -/// -/// This implements the stability condition check: a woman will switch partners -/// if she prefers the new proposer over her current partner. -/// -/// # Arguments -/// * `state` - Current problem state -/// * `woman_id` - ID of the woman making the choice -/// * `new_man_id` - ID of the new proposer -/// * `current_man_id` - ID of her current partner -/// -/// # Returns -/// `true` if the woman prefers the new man, `false` otherwise -/// -/// # Stability Theory -/// This function implements the core stability check. A matching is stable -/// if no woman would prefer to switch from her current partner to any man -/// who would also prefer to switch to her. -fn woman_prefers_new_man(state: &StableMatchingProblem, woman_id: u32, new_man_id: u32, current_man_id: u32) -> bool { - state.preferences.get(&woman_id) - .map(|woman_prefs| { - let new_pos = woman_prefs.ordered_ids.iter().position(|&id| id == new_man_id); - let current_pos = woman_prefs.ordered_ids.iter().position(|&id| id == current_man_id); - - match (new_pos, current_pos) { - (Some(new_p), Some(current_p)) => new_p < current_p, - _ => false, - } - }) - .unwrap_or(false) -} - -/// Creates a single state transition for the Gale-Shapley algorithm. -/// -/// This function encapsulates one iteration of the algorithm: -/// 1. Find a free man -/// 2. Find his next preferred woman to propose to -/// 3. Handle the proposal (engage, reject, or switch partners) -/// -/// The function is pure in the sense that it returns a state computation -/// rather than directly mutating state. -/// -/// # Returns -/// A State monad computation that performs one algorithm step -/// -/// # Algorithm Correctness -/// Each step maintains the algorithm invariants: -/// - Each woman is engaged to at most one man -/// - Men propose in preference order -/// - Women always accept better proposals -fn update_state() -> State { - State::new(|mut state: StableMatchingProblem| { - if let Some(man_id) = get_next_free_man(&state) { - if let Some(woman_id) = find_next_proposal_target(&state, man_id) { - // Record the proposal - state.proposal_history.get_mut(&man_id).unwrap().insert(woman_id); - - match state.engagements.get(&woman_id) { - None => { - // Woman is free, engage - state.engagements.insert(woman_id, man_id); - state.free_men.remove(&man_id); - } - Some(¤t_man_id) => { - // Check if woman prefers new man - if woman_prefers_new_man(&state, woman_id, man_id, current_man_id) { - // Switch engagements - state.engagements.insert(woman_id, man_id); - state.free_men.remove(&man_id); - state.free_men.insert(current_man_id); - } - // Otherwise, man remains free - } - } - } - } - ((), state) - }) -} - -/// Solves the stable matching problem using functional composition. -/// -/// This function repeatedly applies the state transformation until no free men remain, -/// implementing the complete Gale-Shapley algorithm through monadic composition. -/// -/// # Arguments -/// * `problem` - Initial problem instance with all men free -/// -/// # Returns -/// The solved problem with all participants matched -/// -/// # Algorithm Properties -/// The Gale-Shapley algorithm guarantees: -/// - **Termination**: The algorithm always terminates in O(n²) proposals -/// - **Stability**: The resulting matching is stable (no blocking pairs) -/// - **Optimality**: The matching is man-optimal and woman-pessimal -/// -/// # Examples -/// -/// ``` -/// # use crate::{generate_random_instance, solve_stable_matching}; -/// let problem = generate_random_instance(4)?; -/// let solution = solve_stable_matching(problem); -/// -/// // Verify all men are matched -/// assert_eq!(solution.free_men.len(), 0); -/// assert_eq!(solution.engagements.len(), 4); -/// # Ok::<(), &'static str>(()) -/// ``` -//pub fn solve_stable_matching(mut problem: StableMatchingProblem) -> StableMatchingProblem { -// while !problem.free_men.is_empty() { -// let (_, new_state) = update_state().run_state(problem); -// problem = new_state; -// } -// problem -//} - -/// Solves the stable matching problem using functional unfold composition. -/// -/// This implementation uses `std::iter::successors` to express the algorithm -/// as an unfold (anamorphism) - generating successive problem states from -/// the initial configuration until convergence to a stable matching. -/// -/// # Arguments -/// * `problem` - Initial problem instance with all men free -/// -/// # Returns -/// The solved problem with all participants matched -/// -/// # Algorithm Complexity -/// - Time: O(n²) in worst case -/// - Space: O(n) for state representation -/// -/// # Functional Programming Note -/// This demonstrates the unfold pattern - the categorical dual of fold. -/// While fold consumes structure to produce values, unfold generates -/// structure from an initial seed value. -/// -/// # Examples -/// -/// ``` -/// # use crate::{generate_random_instance, solve_stable_matching}; -/// let problem = generate_random_instance(4)?; -/// let solution = solve_stable_matching(problem); -/// -/// assert_eq!(solution.free_men.len(), 0); -/// assert_eq!(solution.engagements.len(), 4); -/// # Ok::<(), &'static str>(()) -/// ``` -pub fn solve_stable_matching(problem: StableMatchingProblem) -> StableMatchingProblem { - std::iter::successors(Some(problem), |current_problem| { - if current_problem.free_men.is_empty() { - None // Algorithm has converged - no more states to generate - } else { - // Generate next state using monadic state transformation - let (_, next_state) = update_state().run_state(current_problem.clone()); - Some(next_state) - } - }) - .last() // Extract the final converged state - .expect("Iterator should always yield at least the initial state") -} - -/// Generates a random stable matching problem instance for testing and experimentation. -/// -/// This function creates a problem with the specified number of men and women, -/// where each person has a random preference ordering over all potential partners. -/// -/// # Arguments -/// * `count` - Number of men and women to create (total 2×count participants) -/// -/// # Returns -/// * `Ok(StableMatchingProblem)` - Random problem instance ready to solve -/// * `Err(&'static str)` - Error if problem creation fails -/// -/// # Randomization -/// Uses Fisher-Yates shuffle to create uniformly random preference orderings, -/// ensuring each possible preference profile has equal probability. -/// -/// # Examples -/// -/// ``` -/// # use crate::generate_random_instance; -/// // Create a problem with 5 men and 5 women -/// let problem = generate_random_instance(5)?; -/// -/// assert_eq!(problem.men.len(), 5); -/// assert_eq!(problem.women.len(), 5); -/// assert_eq!(problem.preferences.len(), 10); // 5 + 5 -/// # Ok::<(), &'static str>(()) -/// ``` -/// -/// # Use Cases -/// - **Testing**: Generate test cases for algorithm verification -/// - **Benchmarking**: Create instances for performance analysis -/// - **Research**: Study algorithm behavior on random instances -pub fn generate_random_instance(count: usize) -> Result { - let mut rng = rand::thread_rng(); - - // Create people using functional combinators - let men: Vec = (1..=count as u32) - .map(|id| Person { id, gender: Gender::Male }) - .collect(); - - let women: Vec = (1..=count as u32) - .map(|id| Person { id, gender: Gender::Female }) - .collect(); - - let mut preferences = HashMap::new(); - - // Generate men's preferences functionally - for man in &men { - let mut women_ids: Vec = (1..=count as u32).collect(); - women_ids.shuffle(&mut rng); - - let prefs = Preferences::new(man.id, women_ids)?; - preferences.insert(man.id, prefs); - } - - // Generate women's preferences functionally - for woman in &women { - let mut men_ids: Vec = (1..=count as u32).collect(); - men_ids.shuffle(&mut rng); - - let prefs = Preferences::new(woman.id, men_ids)?; - preferences.insert(woman.id, prefs); - } - - StableMatchingProblem::new(men, women, preferences) -} - -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn test_preferences_creation() { - let prefs = Preferences::new(1, vec![2, 3, 4]).unwrap(); - assert_eq!(prefs.most_preferred(), 2); - assert!(prefs.prefers(2, 3).unwrap()); - assert!(!prefs.prefers(4, 2).unwrap()); - } - - #[test] - fn test_problem_creation() { - let men = vec![ - Person { id: 1, gender: Gender::Male }, - Person { id: 2, gender: Gender::Male }, - ]; - let women = vec![ - Person { id: 1, gender: Gender::Female }, - Person { id: 2, gender: Gender::Female }, - ]; - - let mut preferences = HashMap::new(); - preferences.insert(1, Preferences::new(1, vec![1, 2]).unwrap()); // Man 1 prefs - preferences.insert(2, Preferences::new(2, vec![2, 1]).unwrap()); // Man 2 prefs - - let problem = StableMatchingProblem::new(men, women, preferences).unwrap(); - assert_eq!(problem.free_men.len(), 2); - } - - #[test] - fn test_generate_random_instance() { - // Generate a small test instance (e.g., 4 men and 4 women) - let n = 4; - let result = generate_random_instance(n); - - assert!( - result.is_ok(), - "generate_random_instance returned an error: {:?}", - result.err() - ); - - let instance = result.unwrap(); - - // Check men and women count - assert_eq!(instance.men.len(), n, "Incorrect number of men generated [attached_file:1]"); - assert_eq!(instance.women.len(), n, "Incorrect number of women generated [attached_file:1]"); - - // Check that preferences exist for each man and woman - for man in &instance.men { - assert!( - instance.preferences.contains_key(&man.id), - "Preference list missing for man {} [attached_file:1]", - man.id - ); - let prefs = instance.preferences.get(&man.id).unwrap(); - // Preferences should list all women without duplicates - assert_eq!( - prefs.ordered_ids.len(), - n, - "Man {} preferences should have length {} [attached_file:1]", - man.id, - n - ); - let mut sorted = prefs.ordered_ids.clone(); - sorted.sort(); - sorted.dedup(); - assert_eq!( - sorted.len(), - n, - "Man {} preferences contain duplicates [attached_file:1]", - man.id - ); - } - - for woman in &instance.women { - assert!( - instance.preferences.contains_key(&woman.id), - "Preference list missing for woman {} [attached_file:1]", - woman.id - ); - let prefs = instance.preferences.get(&woman.id).unwrap(); - assert_eq!( - prefs.ordered_ids.len(), - n, - "Woman {} preferences should have length {} [attached_file:1]", - woman.id, - n - ); - let mut sorted = prefs.ordered_ids.clone(); - sorted.sort(); - sorted.dedup(); - assert_eq!( - sorted.len(), - n, - "Woman {} preferences contain duplicates [attached_file:1]", - woman.id - ); - } - - // Ensure free_men are all the men - for man in &instance.men { - assert!( - instance.free_men.contains(&man.id), - "Man {} should be free initially [attached_file:1]", - man.id - ); - } - - // Ensure proposal_history is initialized for all men and is empty - for man in &instance.men { - let history = instance.proposal_history.get(&man.id).unwrap(); - assert!( - history.is_empty(), - "Proposal history for man {} should be empty [attached_file:1]", - man.id - ); - } - } - - /// Test that demonstrates the documented API usage - #[test] - fn test_basic_functionality() -> Result<(), &'static str> { - let problem = generate_random_instance(3)?; - let solution = solve_stable_matching(problem); - - // All men should be matched - assert_eq!(solution.free_men.len(), 0); - assert_eq!(solution.engagements.len(), 3); - - Ok(()) - } -} - -- 2.49.1