This is how I would tackle this problem.
This implementation is based quite a bit on the F# implementation on RosettaCode, but then translated to idiomatic Elixir and documented.
defmodule GaleShapley do
@moduledoc """
An implementation of the Gale-Shapley algorithm to the 'stable marriage ' problem.
Based on the F#-implementation found on RosettaCode: https://rosettacode.org/wiki/Stable_marriage_problem#F.23
As currently written, expects the men/women to be strings, numbers, or other datastructures where 'identity' 'and 'equality' is the same notion.
"""
defmodule State do
@moduledoc """
Stores the state threaded through the Gale-Shapley algorithm.
- `men`/`women`: List of all men resp. (names)
- `preferences`: Map containing a `men:` and `women:` field, following the guidelines set in `new/2`.
- `proposed:` Keeps track for all men whom they have proposed to so far (because they only propose to a woman once.)
- `wife_of`/`husband_of`: Keeps track of the current pairings.
"""
defstruct [
men: [],
women: [],
preferences: %{men: %{}, women: %{}},
proposed: %{},
wife_of: %{},
husband_of: %{}
]
@doc """
Construct a new state based on the given preferences.
Expects:
- `men_preferences` to be a map of strings to list-of-strings,
- `women_preferences` to be a map of strings to list-of-strings,
- All keys of one map need to be contained in all of the lists of the values of the other, and vice-versa
(i.e., all men have sorted all women according to their preference, and all women have sorted all men according to their preference,
without any people being left out.)
"""
def new(men_preferences, women_preferences) do
men = Map.keys(men_preferences) |> Enum.sort()
women = Map.keys(women_preferences) |> Enum.sort()
%__MODULE__{
men: men,
women: women,
preferences: %{men: men_preferences, women: women_preferences},
proposed: %{},
wife_of: %{},
husband_of: %{}
}
end
@doc """
Keeps track of a pending engagement between a man and a woman.
Returns the altered state
"""
def engage(state, man, woman) do
state
|> put_in([Access.key(:wife_of), man], woman)
|> put_in([Access.key(:husband_of), woman], man)
end
@doc """
Removes a pending engagement between a man and a woman.
Returns the altered state
"""
def disengage(state, woman) do
man = state.husband_of[woman]
state
|> pop_in_([Access.key(:wife_of), man])
|> pop_in_([Access.key(:husband_of), woman])
end
# Helper function because we are not interested in the removed values
defp pop_in_(data, keys) do
{_, altered_data} = pop_in(data, keys)
altered_data
end
def store_proposal(state, man, woman) do
update_in(state, [Access.key(:proposed), Access.key(man, [])], &[woman | &1])
end
end
@doc """
True if `man` is not currently engaged (as seen in `state`)
"""
def free_man?(state, man) do
state.wife_of[man] == nil
end
@doc """
True if `woman ` is not currently engaged (as seen in `state`)
"""
def free_woman?(state, woman) do
state.husband_of[woman] == nil
end
@doc """
True if `man` has proposed to `woman ` (as seen in `state`), false otherwise.
"""
def proposed_to?(state, man, woman) do
state.proposed
|> Map.get(man, [])
|> Enum.member?(woman)
end
@doc """
Returns the list of all women in `women` not yet proposed to by `man` (as seen in `state`)
"""
def unproposed_women(state, man, women) do
Enum.reject(women, &proposed_to?(state, man, &1))
end
@doc """
Checks the preferences of `subject`.
True if `subject` prefers `candidate1` over `candidate2`, false otherwise
"""
def prefers(preferences, subject, candidate1, candidate2) do
candidate_score = fn candidate -> Enum.find_index(preferences[subject], &(&1 == candidate)) end
candidate_score.(candidate1) > candidate_score.(candidate2)
end
@doc """
Specialized version of prefers/4 for men
"""
def prefers_first_woman?(state, man, woman1, woman2) do
prefers(state.preferences.men, man, woman1, woman2)
end
@doc """
Specialized version of prefers/4 for women
"""
def prefers_first_man?(state, woman, man1, man2) do
prefers(state.preferences.women, woman, man1, man2)
end
@doc """
All women `man` prefers over his current fiancée.
"""
def women_to_leave_fiancee_for(state, man) do
fiancee = state.wife_of[man]
state.women
|> Enum.filter(&prefers_first_woman?(state, man, &1, fiancee))
end
@doc """
True iff there is a better woman (c.f. `women_to_leave_fiancee_for`),
which will also prefer `man` over her current fiancée
"""
def better_match_exists?(state, man) do
state
|> women_to_leave_fiancee_for(man)
|> Enum.any?(&prefers_first_man?(state, &1, man, state.husband_of(&1)))
end
def stable_problem?(state) do
state.men
|> Enum.any?(&better_match_exists?(state, &1))
|> Kernel.not()
end
def propose(state, man, woman) do
state
|> State.store_proposal(man, woman)
|> do_propose(man, woman)
end
defp do_propose(state, man, woman) do
cond do
free_woman?(state, woman) ->
State.engage(state, man, woman)
prefers_first_man?(state, woman, man, state.husband_of[woman]) ->
state
|> State.disengage(woman)
|> State.engage(man, woman)
true ->
state
end
end
@doc """
All elegible bachelors
are men who currently are not engaged.
"""
def bachelors(state) do
state.men
|> Enum.filter(&free_man?(state, &1))
|> Enum.filter(&unproposed_women(state, &1, state.women))
end
@doc """
Runs a single step of the Gale-Shapley algorithm,
in which a single man proposes to a single woman.
Should maybe be called for debugging. `run/2` is a higher-level wrapper around this function.
NOTE: This function currently is relatively slow because:
- _all_ bachelors are calculated, but only the first one is used
- _all_ candidates of this bachelor are looked up, but only the first one is used.
Even though this could be improved, in practice (benchmark to be sure!) it probably still only is a constant time overhead
w.r.t. the full running time of the algorithm.
"""
def run_step(state) do
case bachelors(state) do
[] ->
{:done, state}
[bachelor | _other_bachelors] ->
candidate = state
|> unproposed_women(bachelor, state.preferences.men[bachelor])
|> hd
{:next, propose(state, bachelor, candidate)}
end
end
defp run_to_completion(state) do
case run_step(state) do
{:done, state} -> state
{:next, state} -> run_to_completion(state)
end
end
@doc """
Runs the Gale-Shapley algorithm, given two maps of preferences.
See `State.new/2` for the expected format of these preference maps.
"""
def run(men_preferences, women_preferences) do
State.new(men_preferences, women_preferences)
|> run_to_completion
end
defmodule Example do
def men_preferences do
%{
"abe" => ["abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"],
"bob" => ["cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"],
"col" => ["hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"],
"dan" => ["ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"],
"ed" => ["jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"],
"fred" => ["bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"],
"gav" => ["gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"],
"hal" => ["abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"],
"ian" => ["hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"],
"jon" => ["abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"]
}
end
def women_preferences do
%{
"abi" => ["bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"],
"bea" => ["bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"],
"cath" => ["fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"],
"dee" => ["fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"],
"eve" => ["jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"],
"fay" => ["bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"],
"gay" => ["jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"],
"hope" => ["gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"],
"ivy" => ["ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"],
"jan" => ["ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"]
}
end
end
end
