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!

This is equivalent to Map.take(state, men_keys)

this might help:

https://erlang.org/doc/man/digraph.html

especially note:

A digraph is a mutable data structure.

Also unrelated pedantry (sorry, this is a pet obession of mine) is_ functions should be reserved for guards; postifx sigil ...? (like ruby) is the idiomatic way to indicate a boolean function in elixir.

But thank you for pointing me in the right direction, I actually found the culprit code:

  def match(men, _women, state, true) do
    state
    |> Map.to_list()
    |> Enum.slice(0..(length(Map.keys(men)) - 1))
  end

Since I have both men and women in state, I cannot simply discard the state to only keep men-pairs like this. This works for the first test case but not the second one.

I ended up changing it like so:

  def match(men, _women, state, true) do
    men_keys = Map.keys(men)
    for {k, v} <- state, k in men_keys, do: {k, v}
  end

So from the state, I only keep the men keys and put them into a tuple with thier fiancée.

And now the Rosetta Code’s test case passes!

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