stable_matching

Implementation of the Gale-Shapley algorithm, as described on page 6 of Algorithm Design by Kleinberg and Tardos.

Client supplies two slices representing each of the two groups seeking a match, and distance functions indicating preferences. A Vec of pairs of slice indices is returned to indicate the stable matches.

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contributions

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

lib.rs:

The stable_matching_distance() function implements the Gale-Shapley algorithm, as described on page 6 of Algorithm Design by Kleinberg and Tardos.

The client supplies a distance function. Preferences are ranked in terms of distance function values, with lower values indicating higher preferences. When calculating preferences, the member of the proposing group is the first argument, and the member of the proposal-receiving group is the second argument.

The value function will be called at most twice for each proposer-receiver pair.

The function returns a Vec containing pairs of indices of elements of the groups. The first element in the pair is an index into the proposing group slice, and the second element is an index into the proposal-receiving group slice.

The groups may be of different sizes. In those cases, everyone in the smaller group will have a match with someone in the larger group, but there will be unmatched leftovers in the larger group.

In the event of a tie between two proposers competing for the same receiver, the receiver will maintain their current match.

Proposers are placed in a queue in order of appearance in the input slice. Each maintains a queue of proposal-receivers, with ties broken by maintaining the order of the input slice. When a proposed match is broken, the proposer is sent to the back of the queue.

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)]);

If the members of different groups have different preference functions, the stable_matching_asymmetric() function may be used to supply these distinct preference functions.

In the example below, the receiving group preference is for even numbers to match even, and odd numbers to match odd. Because this implementation will not break a match in the event of a tie in preferences, once a receiver has received a proposal from a proposer with the same evenness/oddness, it will always stick with that proposer.

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)]);