Solve the Stable marriage problem using the Gale/Shapley algorithm.


Problem description

Given an equal number of men and women to be paired for marriage, each man ranks all the women in order of his preference and each woman ranks all the men in order of her preference.

A stable set of engagements for marriage is one where no man prefers a woman over the one he is engaged to, where that other woman also prefers that man over the one she is engaged to. I.e. with consulting marriages, there would be no reason for the engagements between the people to change.

Gale and Shapley proved that there is a stable set of engagements for any set of preferences and the first link above gives their algorithm for finding a set of stable engagements.


Task Specifics

Given ten males:

   abe, bob, col, dan, ed, fred, gav, hal, ian, jon

And ten females:

   abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan

And a complete list of ranked preferences, where the most liked is to the left:

  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
   
  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

 Use the Gale Shapley algorithm to find a stable set of engagements
 Perturb this set of engagements to form an unstable set of engagements then check this new set for stability.

References

 The Stable Marriage Problem. (Eloquent description and background information).
 Gale-Shapley Algorithm Demonstration.
 Another Gale-Shapley Algorithm Demonstration.
 Stable Marriage Problem - Numberphile (Video).
 Stable Marriage Problem (the math bit) (Video).
 The Stable Marriage Problem and School Choice. (Excellent exposition)


#!/usr/bin/env bash
main() {
  # Our ten males:
  local males=(abe bob col dan ed fred gav hal ian jon)
 
  # And ten females:
  local females=(abi bea cath dee eve fay gay hope ivy jan)
 
  # Everyone's preferences, ranked most to least desirable:
  local  abe=( abi  eve  cath ivy  jan  dee  fay  bea  hope gay )
  local  abi=( bob  fred jon  gav  ian  abe  dan  ed   col  hal )
  local  bea=( bob  abe  col  fred gav  dan  ian  ed   jon  hal )
  local  bob=(cath  hope abi  dee  eve  fay  bea  jan  ivy  gay )
  local cath=(fred  bob  ed   gav  hal  col  ian  abe  dan  jon )
  local  col=(hope  eve  abi  dee  bea  fay  ivy  gay  cath jan )
  local  dan=( ivy  fay  dee  gay  hope eve  jan  bea  cath abi )
  local  dee=(fred  jon  col  abe  ian  hal  gav  dan  bob  ed  )
  local   ed=( jan  dee  bea  cath fay  eve  abi  ivy  hope gay )
  local  eve=( jon  hal  fred dan  abe  gav  col  ed   ian  bob )
  local  fay=( bob  abe  ed   ian  jon  dan  fred gav  col  hal )
  local fred=( bea  abi  dee  gay  eve  ivy  cath jan  hope fay )
  local  gav=( gay  eve  ivy  bea  cath abi  dee  hope jan  fay )
  local  gay=( jon  gav  hal  fred bob  abe  col  ed   dan  ian )
  local  hal=( abi  eve  hope fay  ivy  cath jan  bea  gay  dee )
  local hope=( gav  jon  bob  abe  ian  dan  hal  ed   col  fred)
  local  ian=(hope  cath dee  gay  bea  abi  fay  ivy  jan  eve )
  local  ivy=( ian  col  hal  gav  fred bob  abe  ed   jon  dan )
  local  jan=( ed   hal  gav  abe  bob  jon  col  ian  fred dan )
  local  jon=( abi  fay  jan  gay  eve  bea  dee  cath ivy  hope)
 
  # A place to store the engagements:
  local -A engagements=()
 
  # Our list of free males, initially comprised of all of them:
  local freemales=( "${males[@]}" )
 
  # Now we use the Gale-Shapley algorithm to find a stable set of engagements
 
  # Loop over the free males. Note that we can't use for..in because the body
  # of the loop may modify the array we're looping over
  local -i m=0
  while (( m < ${#freemales[@]} )); do
    local male=${freemales[m]}
    let m+=1
 
    # This guy's preferences
    eval 'local his=("${'"$male"'[@]}")'
 
    # Starting with his favorite
    local -i f=0
    local female=${his[f]}
 
    # Find her preferences
    eval 'local hers=("${'"$female"'[@]}")'
 
    # And her current fiancé, if any
    local fiance=${engagements[$female]}
 
    # If she has a fiancé and prefers him to this guy, look for this guy's next
    # best choice
    while [[ -n $fiance ]] && 
      (( $(index "$male" "${hers[@]}") > $(index "$fiance" "${hers[@]}") )); do
      let f+=1
      female=${his[f]}
      eval 'hers=("${'"$female"'[@]}")'
      fiance=${engagements[$female]}
    done
 
    # If we're still on someone who's engaged, it means she prefers this guy
    # to her current fiancé. Dump him and put him at the end of the free list.
    if [[ -n $fiance ]]; then
      freemales+=("$fiance")
      printf '%-4s rejected %-4s\n' "$female" "$fiance"
    fi
 
    # We found a match! Record it
    engagements[$female]=$male
    printf '%-4s accepted %-4s\n' "$female" "$male"
  done
 
  # Display the final result, which should be stable
  print_couples engagements
 
  # Verify its stability
  print_stable engagements "${females[@]}"
 
  # Try a swap 
  printf '\nWhat if cath and ivy swap partners?\n'
  local temp=${engagements[cath]}
  engagements[cath]=${engagements[ivy]}
  engagements[ivy]=$temp
 
  # Display the new result, which should be unstable
  print_couples engagements
 
  # Verify its instability
  print_stable engagements "${females[@]}"
}
 
# utility function - get index of an item in an array
index() {
  local needle=$1
  shift
  local haystack=("$@")
  local -i i
  for i in "${!haystack[@]}"; do
    if [[ ${haystack[i]} == $needle ]]; then
      printf '%d\n' "$i"
      return 0
    fi
  done
  return 1
}
 
# print the couples from the engagement array; takes name of array as argument
print_couples() {
  printf '\nCouples:\n'
  local keys
  mapfile -t keys < <(eval 'printf '\''%s\n'\'' "${!'"$1"'[@]}"' | sort)
  local female
  for female in "${keys[@]}"; do
    eval 'local male=${'"$1"'["'"$female"'"]}'
    printf '%-4s is engaged to %-4s\n' "$female" "$male"
  done
  printf '\n'
}
 
# print whether a set of engagements is stable; takes name of engagement array
# followed by the list of females
print_stable() {
  if stable "$@"; then
    printf 'These couples are stable.\n'
  else
    printf 'These couples are not stable.\n'
  fi
}
 
# determine if a set of engagements is stable; takes name of engagement array
# followed by the list of females
stable() {
  local dict=$1 
  shift
  eval 'local shes=("${!'"$dict"'[@]}")'
  eval 'local hes=("${'"$dict"'[@]}")'
  local -i i
  local -i result=0
  for (( i=0; i<${#shes[@]}; ++i )); do
    local she=${shes[i]} he=${hes[i]}
    eval 'local his=("${'"$he"'[@]}")'
    local alt
    for alt in "$@"; do
      eval 'local fiance=${'"$dict"'["'"$alt"'"]}'
      eval 'local hers=("${'"$alt"'[@]}")'
      if (( $(index "$she" "${his[@]}") > $(index "$alt" "${his[@]}") 
         && $(index "$fiance" "${hers[@]}") > $(index "$he" "${hers[@]}") ))
       then
        printf '%-4s is engaged to %-4s but prefers %4s, ' "$he" "$she" "$alt"
        printf 'while %-4s is engaged to %-4s but prefers %4s.\n' "$alt" "$fiance" "$he"
        result=1
      fi
    done
  done
  if (( result )); then printf '\n'; fi
  return $result
}
 
main "$@"