GaleShapley.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Algorithms.Problems.StableMarriage
{
    public static class GaleShapley
    {
        /// <summary>
        ///     Finds a stable matching between two equal sets of elements (fills EngagedTo properties).
        ///     time complexity: O(n^2), where n - array size.
        ///     Guarantees:
        ///     - Everyone is matched
        ///     - Matches are stable (there is no better accepter, for any given proposer, which would accept a new match).
        ///     Presented and proven by David Gale and Lloyd Shapley in 1962.
        /// </summary>
        public static void Match(Proposer[] proposers, Accepter[] accepters)
        {
            if (proposers.Length != accepters.Length)
            {
                throw new ArgumentException("Collections must have equal count");
            }

            while (proposers.Any(m => !IsEngaged(m)))
            {
                DoSingleMatchingRound(proposers.Where(m => !IsEngaged(m)));
            }
        }

        private static bool IsEngaged(Proposer proposer) => proposer.EngagedTo is not null;

        private static void DoSingleMatchingRound(IEnumerable<Proposer> proposers)
        {
            foreach (var newProposer in proposers)
            {
                var accepter = newProposer.PreferenceOrder.First!.Value;

                if (accepter.EngagedTo is null)
                {
                    Engage(newProposer, accepter);
                }
                else
                {
                    if (accepter.PrefersOverCurrent(newProposer))
                    {
                        Free(accepter.EngagedTo);
                        Engage(newProposer, accepter);
                    }
                }

                newProposer.PreferenceOrder.RemoveFirst();
            }
        }

        private static void Free(Proposer proposer)
        {
            proposer.EngagedTo = null;
        }

        private static void Engage(Proposer proposer, Accepter accepter)
        {
            proposer.EngagedTo = accepter;
            accepter.EngagedTo = proposer;
        }
    }
}