stable_matching

实现了Kleinberg和Tardos在《算法设计》第6页上描述的Gale-Shapley算法。

客户端提供表示两个寻求匹配的组的两个切片，以及表示偏好的距离函数。返回一个包含切片索引对的Vec，以指示稳定匹配。

许可证

根据以下任一许可证授权：

• Apache License 2.0 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

您自行选择。

贡献

除非您明确表示，否则根据Apache-2.0许可证定义的，您提交给作品的任何有意贡献都将按照上述方式双重授权，不附加任何额外条款或条件。

lib.rs:

该stable_matching_distance()函数实现了Kleinberg和Tardos在《算法设计》第6页上描述的Gale-Shapley算法。

客户端提供距离函数。根据距离函数值对偏好进行排名，值越低表示偏好越高。在计算偏好时，提议组的成员是第一个参数，接受提议组的成员是第二个参数。

对于每个提议-接受者对，值函数最多被调用两次。

函数返回一个包含组元素索引对的Vec。对中的第一个元素是对提议组切片的索引，第二个元素是对接受提议组切片的索引。

组的大小可能不同。在这些情况下，较小组中的每个人都会与较大组中的某个人匹配，但较大组中会有未匹配的剩余人员。

如果有两个提议者竞争同一个接受者，则接受者将保持当前的匹配。

将提议者按输入切片中的出现顺序放入队列。每个提议者都维护一个接受提议者队列，通过保持输入切片的顺序来解决冲突。当提议的匹配被破坏时，提议者将被发送到队列的末尾。

use stable_matching::stable_matching_distance;

let group1: Vec<i64> = vec![1, 2, 3, 4, 5];
let group2: Vec<i64> = vec![8, 9, 10, 11];

let pairs = stable_matching_distance(&group1, &group2, |p1, p2| (p1 - p2).abs());
assert_eq!(pairs, vec![(4, 0), (3, 1), (2, 2), (1, 3)]);

let pairs = stable_matching_distance(&group2, &group1, |p1, p2| (p1 - p2).abs());
assert_eq!(pairs, vec![(3, 1), (2, 2), (1, 3), (0, 4)]);

如果不同组的成员有不同的偏好函数，可以使用 stable_matching_asymmetric() 函数来提供这些不同的偏好函数。

在下面的示例中，接收组的偏好是偶数匹配偶数，奇数匹配奇数。因为此实现不会在偏好冲突时破坏匹配，一旦接收者从具有相同偶奇性的提议者那里收到提议，它将始终坚持该提议者。

use stable_matching::stable_matching_asymmetric;

let group1: Vec<i64> = vec![1, 2, 3, 4, 5];
let group2: Vec<i64> = vec![8, 9, 10, 11];

let pairs = stable_matching_asymmetric(&group1, |p1, p2| (p1 - p2).abs(), &group2, |p1, p2| if p1 % 2 == p2 % 2 {0} else {1});
assert_eq!(pairs, vec![(1, 0), (0, 1), (3, 2), (2, 3)]);

let group1: Vec<i64> = vec![5, 4, 3, 2, 1];
let pairs = stable_matching_asymmetric(&group1, |p1, p2| (p1 - p2).abs(), &group2, |p1, p2| if p1 % 2 == p2 % 2 {0} else {1});
assert_eq!(pairs, vec![(1, 0), (0, 1), (3, 2), (2, 3)]);