安定な結婚の問題 stable marriage problem

早起きをする事にした.
ラジオ体操とかするのもあれなんで,アルゴリズム体操でもしようかと思う.
 

問題

N人の男性とN人の女性が集団お見合いをし,おのおの異性を好みの順に順位付けした.
この順位表を元に安定な縁結びをしなさい.
 

感想

ただしイケメンに限る
番兵かわいい.
 

コード

N = 3 # 各性の人数
boy = []; girl = []; position = []; rank = []

(1..N).each do |g|
  puts "女性#{g}の好み"
  (1..N).each {|b| rank[g] ||= []; rank[g][b] = gets.to_i }
  boy[g] = 0; rank[g][0] = N + 1;
end

(1..N).each do |b|
  puts "男性#{b}の好み"
  (1..N).each {|r| girl[b] ||= []; girl[b][r] = gets.to_i }
  position[b] = 0
end

(1..N).each do |b|
  s = b
  while(s != 0)
    g = girl[s][position[s]+=1]
    if (rank[g][s] < rank[g][boy[g]])
      t = boy[g]; boy[g] = s; s = t;
    end
  end
end

(1..N).each{|i| puts "#{i} - 男 #{boy[i]}"}

参照

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)