稳定婚姻问题的优雅解法（用Rust实现Gale-Shapley延迟接受算法）

什么是“稳定”？

一个配对是稳定的，当且仅当不存在一对男女（A男，B女），他们各自当前的伴侣都不是对方，但A更喜欢B胜过当前伴侣，同时B也更喜欢A胜过当前伴侣。如果存在这样的“私奔”组合，那么这个配对就是不稳定的。

Gale-Shapley 算法原理

该算法由 David Gale 和 Lloyd Shapley 在1962年提出。其核心思想是：一方主动求婚，另一方根据自己的偏好决定是否接受或拒绝。具体步骤如下：

1. 每个男性向他偏好列表中最靠前且尚未求婚的女性求婚。
2. 每个女性收到多个求婚后，保留她最偏好的那个（如果已有临时伴侣但新求婚者更优，则抛弃旧人），拒绝其他人。
3. 被拒绝的男性继续向下一个偏好的女性求婚。
4. 重复上述过程，直到所有人都配对成功。

这个算法保证最终结果是稳定的，并且对主动求婚的一方（如男性）是最优的。

用 Rust 实现稳定婚姻算法

接下来，我们将用 Rust语言 实现这个算法。Rust 的内存安全、无垃圾回收和强类型系统非常适合这类算法实现。

1. 定义数据结构

我们需要表示人（Person）、他们的偏好列表，以及当前状态。

#[derive(Debug, Clone)]pub struct Person {    pub name: String,    pub preference: Vec<String>, // 偏好列表，从最喜欢到最不喜欢    pub engaged_to: Option<String>,}impl Person {    fn new(name: &str, preference: Vec<&str>) -> Self {        Person {            name: name.to_string(),            preference: preference.into_iter().map(|s| s.to_string()).collect(),            engaged_to: None,        }    }    // 返回下一个未求婚的偏好对象索引    fn next_proposal_index(&self, proposals: &std::collections::HashMap<String, usize>) -> Option<usize> {        let index = proposals.get(&self.name).copied().unwrap_or(0);        if index < self.preference.len() {            Some(index)        } else {            None        }    }}

2. 实现 Gale-Shapley 算法

use std::collections::{HashMap, HashSet};pub fn stable_marriage(men: &mut [Person], women: &mut [Person]) -> HashMap<String, String> {    let mut proposals: HashMap<String, usize> = HashMap::new(); // 记录每个男性已求婚到第几个    let mut free_men: Vec<String> = men.iter().map(|m| m.name.clone()).collect();    let mut woman_map: HashMap<String, &mut Person> = women        .iter_mut()        .map(|w| (w.name.clone(), w))        .collect();    while !free_men.is_empty() {        let man_name = free_men.remove(0);        let man = men.iter_mut().find(|m| m.name == man_name).unwrap();        if let Some(idx) = man.next_proposal_index(&proposals) {            let woman_name = &man.preference[idx];            proposals.insert(man.name.clone(), idx + 1);            if let Some(woman) = woman_map.get_mut(woman_name) {                let current_engagement = &woman.engaged_to;                let prefers_new = match current_engagement {                    None => true,                    Some(current_man) => {                        let current_rank = woman.preference.iter().position(|x| x == current_man);                        let new_rank = woman.preference.iter().position(|x| x == &man.name);                        new_rank.unwrap() < current_rank.unwrap()                    }                };                if prefers_new {                    if let Some(old_man) = &woman.engaged_to {                        // 解除旧配对                        let old_man_ref = men.iter_mut().find(|m| &m.name == old_man).unwrap();                        old_man_ref.engaged_to = None;                        free_men.push(old_man.clone());                    }                    woman.engaged_to = Some(man.name.clone());                    man.engaged_to = Some(woman.name.clone());                } else {                    // 被拒绝，继续留在自由队列                    free_men.push(man.name.clone());                }            }        }    }    // 构建最终配对结果    let mut result = HashMap::new();    for man in men {        if let Some(woman) = &man.engaged_to {            result.insert(man.name.clone(), woman.clone());        }    }    result}

3. 测试示例

fn main() {    let mut men = vec![        Person::new("A", vec!["X", "Y", "Z"]),        Person::new("B", vec!["Y", "X", "Z"]),        Person::new("C", vec!["X", "Y", "Z"])    ];    let mut women = vec![        Person::new("X", vec!["B", "A", "C"]),        Person::new("Y", vec!["A", "B", "C"]),        Person::new("Z", vec!["A", "B", "C"])    ];    let matches = stable_marriage(&mut men, &mut women);    println!("稳定配对结果:");    for (man, woman) in &matches {        println!("{} ↔ {}", man, woman);    }}

运行这段代码，你会得到一个稳定的配对结果。例如：

A ↔ YB ↔ XC ↔ Z

为什么这个算法重要？

Rust稳定婚姻算法不仅是学术上的趣味问题，它在现实中有着深远影响。例如，美国的“国家住院医师匹配计划”（NRMP）就使用类似算法为医学生分配住院医师职位。此外，在学校招生、任务调度等领域也有应用。

通过学习 延迟接受算法 的 Rust 实现，你不仅能掌握一个经典算法，还能深入理解 Rust 的所有权、借用和集合操作等核心概念。这也是为什么 Rust编程教程 中常包含此类算法练习。

总结

本文详细讲解了稳定婚姻问题及其解决方案——Gale-Shapley 算法，并用 Rust 语言完整实现了该算法。无论你是算法初学者还是 Rust 新手，希望这个 配对算法实现 教程能帮助你理解如何将理论转化为高效、安全的代码。

小提示：你可以尝试修改偏好列表，观察配对结果如何变化，进一步验证“稳定性”。