From 2e5fb31c8f3d72510d7c5fca9b0d9e8a31aa6733 Mon Sep 17 00:00:00 2001 From: Jeff Date: Fri, 12 Sep 2025 22:07:36 +0900 Subject: [PATCH 1/1] Initial commit --- .gitignore | 1 + Cargo.lock | 133 ++++++++ Cargo.toml | 7 + src/main.rs | 936 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 1077 insertions(+) create mode 100644 .gitignore create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 src/main.rs diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..ea8c4bf --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +/target diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..fb81a63 --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,133 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "algorithms" +version = "0.1.0" +dependencies = [ + "rand", +] + +[[package]] +name = "cfg-if" +version = "1.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2fd1289c04a9ea8cb22300a459a72a385d7c73d3259e2ed7dcb2af674838cfa9" + +[[package]] +name = "getrandom" +version = "0.2.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "335ff9f135e4384c8150d6f27c6daed433577f86b4750418338c01a1a2528592" +dependencies = [ + "cfg-if", + "libc", + "wasi", +] + +[[package]] +name = "libc" +version = "0.2.175" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6a82ae493e598baaea5209805c49bbf2ea7de956d50d7da0da1164f9c6d28543" + +[[package]] +name = "ppv-lite86" +version = "0.2.21" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "85eae3c4ed2f50dcfe72643da4befc30deadb458a9b590d720cde2f2b1e97da9" +dependencies = [ + "zerocopy", +] + +[[package]] +name = "proc-macro2" +version = "1.0.101" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "89ae43fd86e4158d6db51ad8e2b80f313af9cc74f5c0e03ccb87de09998732de" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "quote" +version = "1.0.40" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1885c039570dc00dcb4ff087a89e185fd56bae234ddc7f056a945bf36467248d" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "rand" +version = "0.8.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404" +dependencies = [ + "libc", + "rand_chacha", + "rand_core", +] + +[[package]] +name = "rand_chacha" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88" +dependencies = [ + "ppv-lite86", + "rand_core", +] + +[[package]] +name = "rand_core" +version = "0.6.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c" +dependencies = [ + "getrandom", +] + +[[package]] +name = "syn" +version = "2.0.106" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ede7c438028d4436d71104916910f5bb611972c5cfd7f89b8300a8186e6fada6" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "unicode-ident" +version = "1.0.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f63a545481291138910575129486daeaf8ac54aee4387fe7906919f7830c7d9d" + +[[package]] +name = "wasi" +version = "0.11.1+wasi-snapshot-preview1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ccf3ec651a847eb01de73ccad15eb7d99f80485de043efb2f370cd654f4ea44b" + +[[package]] +name = "zerocopy" +version = "0.8.27" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0894878a5fa3edfd6da3f88c4805f4c8558e2b996227a3d864f47fe11e38282c" +dependencies = [ + "zerocopy-derive", +] + +[[package]] +name = "zerocopy-derive" +version = "0.8.27" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "88d2b8d9c68ad2b9e4340d7832716a4d21a22a1154777ad56ea55c51a9cf3831" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..c62b0b4 --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,7 @@ +[package] +name = "algorithms" +version = "0.1.0" +edition = "2024" + +[dependencies] +rand = "0.8" diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..4d6a0bf --- /dev/null +++ b/src/main.rs @@ -0,0 +1,936 @@ +//! # 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 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") + } + + /// 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 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