【アルゴリズム】 安定の結婚の問題

安定の結婚の問題

男N人と女N人が合同でお見合いをする。それぞれ好みの異性がいたとする。極力希望を聞いてあげて、この人よりもあの人が良かった、ということを防ぎたい。これがここでいう安定の結婚。

なんだかちょっと乱暴な気がするけれどもね。

「C言語による最新アルゴリズム辞典」を元にお勉強。

とりあえずCで書かれたコードを（ほとんど）そのまま書き直し

とりあえず、Rubyで書き直し。

#!ruby -Ks

input = [
  [3, 2, 1],
  [1, 2, 3],
  [2, 3, 1],
  [3, 2, 1],
  [3, 2, 1],
  [3, 1, 2]
]

rank = Array.new(3 + 1) { Array.new(3 + 1) { 0 } }
girl = Array.new(3 + 1) { Array.new(3 + 0) { 0 } }
boy  = Array.new(3 + 1) { 0 }

position = Array.new(3 + 1) { 0 }

3.times do |g|
  3.times do |r|
    b = input[g][r]
    rank[g + 1][b] = r
  end
  rank[g + 1][0] = 3 + 1
end

3.times do |b|
  3.times do |r|
    girl[b + 1][r + 1] = input[b + 3][r]
  end
end

3.times do |b|
  s = b + 1
  until s == 0
    position[s] += 1
    g = girl[s][position[s]]
    if rank[g][s] < rank[g][boy[g]]
      t = boy[g]
      boy[g] = s
      s = t
    end
  end
end

3.times do |g|
  printf "女 %d - 男 %d\\n", g + 1, boy[g + 1]
end

実行結果は以下のとおり。

女 1 - 男 1
女 2 - 男 2
女 3 - 男 3

変数inputは前3つの要素が女性の好み。後3つは男性の好み。数字が何番目の異性が好みかを示している。ここでの変数inputの例では、1番目の女性がどう考えても貧乏くじを引いているけれど、他の人達は概ね満足する結果になるのではないだろうか。幸せになっていただきたい。

だめだ・・・よくわからない

これはこれで結果が出て嬉しいのだけれど、それぞれの配列（input,boy,girl）がどんな動きをしているのかよくわからなかったので書きなおした。ボクはほんとうにだめだなぁ。

• 男性の女性の好み
• 女性の男性の好み
• お見合いの結果

多次元配列だとうまくイメージしづらい。上の3つをclassにして、一つひとつの動作をメソッドに置き換える。これで、どこでどのような動作をしているのか調べていく作戦で行こうかなと。

#!ruby -Ks

class Boy
  def initialize
    @rank = 0
  end

  def nextBoyRank(boy_number)
    t = @rank
    @rank = boy_number
    t
  end

  attr_accessor :rank
end

class Girl
  def initialize(rank)
    @girl = [0]

    3.times do |r|
      @girl[r + 1] = rank[r]
    end

    @position = 0
  end

  def nextGirlRank
    @position += 1
    @girl[@position]
  end
end

class Rank
  def initialize(input)
    @rank = [3 + 1]

    3.times do |r|
      b = input[r]
      @rank[b] = r
    end
  end

  def wouldYouMarryMe?(boy_number, boy)
    @rank[boy_number] < @rank[boy.rank]
  end
end

input = [
  [2, 3, 1],
  [2, 1, 3],
  [3, 2, 1],
  [1, 3, 2],
  [3, 2, 1],
  [3, 1, 2]
]

# 女性の好み
rank = Array.new(3 + 1) {|g| g == 0 ? nil : Rank.new(input[g - 1]) }

# 男性の好み
girl = Array.new(3 + 1) {|b| b == 0 ? nil : Girl.new(input[b + (3 - 1)]) }

# 結婚の結果
boy  = Array.new(3 + 1) {|i| Boy.new }

3.times do |b|
  boy_number = b + 1

  until boy_number == 0
    g = girl[boy_number].nextGirlRank

    # 結婚を申し込んでみる。女性側は他に男性がいない時 or 男性がより素晴らしければにプロポーズを承諾する
    if rank[g].wouldYouMarryMe?(g, boy[g])
      # 結婚を承諾されたら、boy_numberは0になり、次 or 振られた男性の順番になる
      boy_number = boy[g].nextBoyRank(boy_number)
    end
  end
end

3.times do |g|
  printf "女 %d - 男 %d\\n", g + 1, boy[g + 1].rank
end

わかったこと

配列girl、rankのキーが自分自身で、値がランクになる。girlが「男性の女性の好みのランク」であり、rankが「女性の好みのランク」であるという点が結構ややこしいと感じてしまった。girlって言ったらそのまま「女性のランク」と受け取ってしまいそうで…

結婚の結果が、boyという配列な点も結構ややこしかった。確かに、boyは女nと結婚した男なのだが、girlの反対はboyなもんで同列のデータと扱ってしまったと勘違いしていた。

自分なりにわかりやすく書いたソースのお陰で原理が分かった。やはり、変数名は何をしているのか分かるような名前をつけるとわかりやすくなる。それだけなんだけど結構重要だな。

2012/07/28 17:36