How would you implement the Gale-Shapley algorithm in Elixir for solving the Stable Marriage Problem?

It looks like you’re doing it very similarly to how I would. Is your code failing the tests?

Yes it is failing the Rosetta Code test case (the one with the real names, not just the letters).

I think it’s because if a man is not available, I still pop his favorite woman from his preference list, even though he did not technically proposed to her. A man propose to a woman only if he is available.

I tried to not pop the favorite woman out of the preference list for this case, but it still did not work.

this might help:

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.

What is stopping you from skipping over the unavailable men each round and not considering their favored women at all?

Also, I agree with @ityonemo that the is_ prefix should be replaced by a ? suffix for booleans.

I would like to avoid relying on ETS right now and would rather try to do it the functional way.

But using digraph for solving this problem is definitely something that I’d like to explore later.

I did try like this:

defmodule StableMarriage do
  def match(men, women, state \\ %{}, is_stable \\ false)

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

  def match(men, women, state, false) do
    {new_men, state} =
      Enum.reduce(men, {men, state}, fn
        {m1, [w | preferences]}, {men, state} ->
          if m1_single? = !state[m1] do
            w_single? = !state[w]
            m2 = if w_single?, do: nil, else: state[w]

            new_state =
              case {m1_single?, w_single?, m1_prefered_to_m2?(women, w, m1, m2)} do
                {true, true, true} -> state |> Map.put(m1, w) |> Map.put(w, m1)
                {true, false, true} -> state |> Map.delete(m2) |> Map.put(m1, w) |> Map.put(w, m1)
                _ -> state
              end

            {_men = %{men | m1 => preferences}, new_state}
          else
            {men, state}
          end
      end)

    match(new_men, women, state, is_stable(men, state))
  end

  def m1_prefered_to_m2?(_women, _woman, _m1, nil) do
    true
  end

  def m1_prefered_to_m2?(women, woman, m1, m2) do
    Enum.find_index(women[woman], &(&1 == m1)) <
      Enum.find_index(women[woman], &(&1 == m2))
  end

  def is_stable(men, state) do
    length(Map.keys(men)) * 2 == length(Map.keys(state))
  end
end

But surprisingly, I get some pairs in the wrong order/or in doubles in the final result while some other pairs are missing:

     test/stable_marriage_test.exs:4
     Assertion with in failed
     code:  assert {"jon", "abi"} in matches
     left:  {"jon", "abi"}
     right: [{"abe", "ivy"}, {"abi", "jon"}, {"bea", "fred"}, {"bob", "cath"}, {"cath", "bob"}, {"col", "dee"}, {"dan", "fay"}, {"dee", "col"}, {"ed", "jan"}, {"eve", "hal"}]
     stacktrace:
       test/stable_marriage_test.exs:61: (test)

That looks to be from this code:

case {m1_single?, w_single?, m1_prefered_to_m2?(women, w, m1, m2)} do
  {true, true, true} -> state |> Map.put(m1, w) |> Map.put(w, m1)
  {true, false, true} -> state |> Map.delete(m2) |> Map.put(m1, w) |> Map.put(w, m1)
  _ -> state
end

Where sometimes you are using the man as the key (and woman as value) and other times you are adding the woman as the key (and man as value). I think you need to keep that consistent.

The state variable holds the pairs from man to woman and woman to man. So if “a” and “z” forms a couple, the state map will have %{"a" => "z", "z" => "a"}. I need this to be able to find the current fiancé of any given woman.

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!

Nice work!