gale-shapley-rs

该代码实现了加莱-夏普利算法，用于解决稳定婚姻问题，这是博弈论和经济学中的一个经典问题。该问题涉及将一组男性和女性匹配成稳定的婚姻，其中稳定的婚姻定义为不存在两对异性伴侣都宁愿选择对方而不是他们当前的伴侣。

算法

该算法的工作原理如下：首先，每个男人向最喜欢的一位女性求婚。如果该女性尚未订婚，她将接受求婚，两人成为订婚关系。如果该女性已经与另一位男性订婚，她将比较她的当前伴侣与新的求婚者，并选择她更喜欢的男性。被拒绝的男性将自由地向他的下一个首选女性求婚。这个过程会继续进行，直到所有男性都订婚，此时算法终止，并返回当前的订婚关系作为稳定的婚姻。

该算法保证对所有输入都终止并找到稳定的婚姻，并且输出也是唯一的。

命令行使用

以文本形式解决问题

从终端运行程序

$ ./galeshapley

以以下格式输入你的问题

Joe: Jane Isabelle
Jack: Isabelle Jane
Isabelle: Joe Jack
Jane: Joe Jack

然后留下一个空行，等待以以下形式的响应

Joe: Jane
Jack: Isabelle

计算统计数据

计算在 N 个男性和 N 个女性的问题中，男性成为稳定婚姻中首选伴侣的概率。

运行

./galeshapley 500

它将显示计算结果

Solving problems with 3 men and 3 women with random preferences.
Success rate for the first man (got first choice / total samples) :    849579/  1330450 = 63.856515%

程序化使用

实现

GaleShapley 结构体代表算法本身，它有几个方法用于实现算法的不同步骤。`init` 方法用于初始化算法所需的数据结构，例如男性和女性的偏好。`find_stable_marriage` 方法运行算法并返回最终的稳定婚姻。

示例

let men_preferences = vec![vec![0, 1], vec![0, 1]]; // both men prefer woman 0
let women_preferences = vec![vec![1, 0], vec![1, 0]]; // both women prefer man 1
        
let stable_marriages: Vec<(Man, Woman)> = GaleShapley::init(men_preferences, women_preferences)
            .find_stable_marriage()
            .collect();