stableMatching function

Map<String, String> stableMatching(StableMatchingPrefs prefs)

Computes a stable matching from prefs, returning proposer → acceptor for every matched proposer; unmatched proposers are absent from the map.

Proposer-optimal: each proposer receives the best partner it attains in any stable matching. Incomplete lists mean a party may end unmatched rather than pair with someone it did not rank. Throws ArgumentError when a preference list names an unknown party or repeats a party (ties are disallowed).

Example:

stableMatching((
  proposers: {'a': ['x', 'y'], 'b': ['x', 'y']},
  acceptors: {'x': ['a', 'b'], 'y': ['a', 'b']},
)); // {'a': 'x', 'b': 'y'}

Audited: 2026-06-12 11:26 EDT

Implementation

Map<String, String> stableMatching(StableMatchingPrefs prefs) {
  _validate(prefs);
  // Precompute each acceptor's rank map so it can compare two suitors in
  // constant time instead of re-scanning its preference list on every proposal.
  final Map<String, Map<String, int>> ranks = _acceptorRanks(prefs.acceptors);
  // matchOf maps acceptor → currently matched proposer (tentative until a better
  // suitor displaces it).
  final Map<String, String> matchOf = <String, String>{};
  // Free proposers still holding an index into their own preference list; each
  // proposer only ever moves DOWN its list, which bounds total proposals.
  final List<String> free = prefs.proposers.keys.toList();
  final Map<String, int> nextChoice = <String, int>{
    for (final String p in free) p: 0,
  };
  while (free.isNotEmpty) {
    final String proposer = free.removeLast();
    final List<String> choices = prefs.proposers[proposer] ?? const <String>[];
    _propose(proposer, choices, ranks, matchOf, nextChoice, free);
  }
  // Invert acceptor → proposer into the documented proposer → acceptor result.
  return <String, String>{
    for (final MapEntry<String, String> e in matchOf.entries) e.value: e.key,
  };
}