This is equivalent to Map.take(state, men_keys)
dimitarvp
lud
I made a quick’n’dirty implementation for fun:
defmodule GS do
def run(males, females) do
proposers = prepare(males)
acceptors = prepare(females)
loop(proposers, acceptors)
end
defp prepare(prefmap) do
Enum.into(prefmap, %{}, fn {name, prefs} -> {name, %{prefs: prefs, best: nil}} end)
end
defp loop(proposers, acceptors) do
Enum.reduce(
proposers,
[],
fn
{man_name, %{best: nil}}, acc -> [man_name | acc]
_, acc -> acc
end
)
|> case do
[] ->
{proposers, acceptors}
single_men ->
{proposers, acceptors} = round(proposers, acceptors, single_men)
loop(proposers, acceptors)
end
end
defp round(proposers, acceptors, single_men) do
# for each men, propose to their best choice
Enum.reduce(single_men, {proposers, acceptors}, fn man_name, {proposers, acceptors} ->
man = proposers[man_name]
[woman_name | less_prefered_woman] = man.prefs
woman = acceptors[woman_name]
case propose(woman, man_name) do
{:accept, jilted} ->
proposers = Map.put(proposers, man_name, %{man | best: woman_name})
acceptors = Map.put(acceptors, woman_name, %{woman | best: man_name})
proposers =
if jilted do
Map.update!(proposers, jilted, fn %{prefs: prefs} ->
%{best: nil, prefs: prefs -- [woman_name]}
end)
else
proposers
end
acceptors =
if jilted do
# this is useless with this implementation because we will never
# call propose() that man with tha woman again
Map.update!(acceptors, woman_name, fn %{prefs: prefs} = woman ->
%{woman | prefs: prefs -- [jilted]}
end)
else
acceptors
end
{proposers, acceptors}
:reject ->
proposers = Map.put(proposers, man_name, %{man | prefs: less_prefered_woman})
acceptors = Map.put(acceptors, woman_name, %{woman | prefs: woman.prefs -- [man_name]})
{proposers, acceptors}
end
end)
end
defp propose(%{best: nil}, _man_name), do: {:accept, nil}
defp propose(%{best: best, prefs: prefs}, man_name), do: propose(best, prefs, man_name)
defp propose(best, [man_name | _], man_name), do: {:accept, best}
defp propose(best, [best | _], _man_name), do: :reject
defp propose(best, [_other | rest], man_name), do: propose(best, rest, man_name)
end
ExUnit.start()
defmodule GSTest do
use ExUnit.Case
test "video dataset" do
males = %{
"A" => ~w(O M N L P),
"B" => ~w(P N M L O),
"C" => ~w(M P L O N),
"D" => ~w(P M O N L),
"E" => ~w(O L M N P)
}
females = %{
"L" => ~w(D B E C A),
"M" => ~w(B A D C E),
"N" => ~w(A C E D B),
"O" => ~w(D A C B E),
"P" => ~w(B E A C D)
}
result = GS.run(males, females)
IO.inspect(result, label: "result")
assert {%{
"A" => %{best: "O"},
"B" => %{best: "P"},
"C" => %{best: "N"},
"D" => %{best: "M"},
"E" => %{best: "L"}
},
%{
"L" => %{best: "E"},
"M" => %{best: "D"},
"N" => %{best: "C"},
"O" => %{best: "A"},
"P" => %{best: "B"}
}} = result
end
end
It could be best with mapsets instead of lists for preferences, and refactoring the big reduce loop into smaller functions, but it works.
1
Qqwy
TypeCheck Core Team
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
2
bradley
Prior to seeing this blog post I wrote an implementation that passes the RosettaCode checks.
defmodule GaleShapley do
@moduledoc """
Implements the Gale–Shapley algorithm for the stable marriage problem.
Wikipedia: https://en.wikipedia.org/wiki/Stable_marriage_problem
Reference video: https://www.youtube.com/watch?v=Qcv1IqHWAzg&t=6s
"""
@spec run(%{term() => [term()]}, %{term() => [term()]}) :: %{term() => term()}
def run(proposers, recipients) do
proposals = propose(proposers)
engagements = become_engaged(proposals, recipients)
if stable_pair?(engagements, recipients) do
engagements
else
proposals
|> recipient_choices()
|> reject_proposals(proposers, engagements)
|> run(recipients)
end
end
# If the amount of tentative engagements is the same
# as the number of recipients we have found all
# stable pairs and the algorithm can terminate
@spec stable_pair?(%{term() => term()}, %{term() => [term()]}) :: boolean()
defp stable_pair?(engagements, recipients),
do: map_size(recipients) == map_size(engagements)
# Creates a data structure that shows what options
# recipients have after they've been proposed to
@spec recipient_choices(%{term() => term()}) :: %{term() => [term()]}
defp recipient_choices(proposals) do
Enum.group_by(
proposals,
fn {_proposer, recipient} -> recipient end,
fn {proposer, _recipient} -> proposer end
)
end
# All proposers propose to their first best option
@spec propose(%{term() => [term()]}) :: %{term() => term()}
defp propose(proposers) do
Enum.into(proposers, %{}, fn {name, _prefs} ->
{name, List.first(proposers[name])}
end)
end
# Recipients become tenatively engaged with their most preferred proposer
# Some recipients may not have engagements yet
@spec become_engaged(%{term() => term()}, %{term() => [term()]}) :: %{term() => term()}
defp become_engaged(proposals, recipients) do
Enum.reduce(recipients, %{}, fn {name, prefs}, recipients_acc ->
first_pick = Enum.find(prefs, fn pref -> proposals[pref] == name end)
if first_pick do
Map.put(recipients_acc, name, first_pick)
else
recipients_acc
end
end)
end
# Reject each proposer that's not the recipient's top pick and update their preferences
# so they won't pick them again in the future.
@spec reject_proposals(%{term() => [term()]}, %{term() => [term()]}, %{term() => term()}) :: %{
term() => [term()]
}
defp reject_proposals(recipient_proposals, proposers, tentative_engagements) do
Enum.reduce(recipient_proposals, proposers, fn {name, proposals}, updated_proposers ->
rejected_proposals =
Enum.reject(proposals, fn proposal -> proposal == tentative_engagements[name] end)
Enum.reduce(rejected_proposals, updated_proposers, fn rejected_proposers, acc ->
new_proposers = List.delete(updated_proposers[rejected_proposers], name)
Map.merge(acc, %{rejected_proposers => new_proposers})
end)
end)
end
end
Looking back I should have ported an existing RosettaCode algorithm because the one I have is recursive and could hang if invalid data is passed in. I do use a form of this in production though so it’s been reliable so far!
Also, I couldn’t get @Qqwy’s solution to work with the RosettaCode checks otherwise I would have used it over mine!
4