アルゴリズムの学習(002/XXX)

　コンピュータ科学を学ぶべくアルゴリズムを学んでいく。参考として定番書であり古典的名著でもある

［改訂新版］C言語による標準アルゴリズム事典 Software Technology

を用いる。実装には勉強もかねてC#を使う。

3.　安定的結婚問題

　女性人、男性人がそれぞれ異性人を好みの順に列挙したの表を入力すると、安定な結婚の解を1つ出力する*1。

	(1)	とする。
	(2)	男性は女性に求婚し、差し当たり女性はこれをOKとし(男性,女性)をペアとする。
	(3)	とする。
	(4)	男性は女性に求婚する。女性は既に求婚された男性が存在する場合、男性よりも好ましいならば男性をそのまま、そうでなければ新たに男性をペアの相手とし、いなければそのまま男性を受け入れる。
	(5)	ならば(3)に戻る。そうでなければアルゴリズムを終了する。

　入力としてとして以下の好みを与えることとする。

		1番目	2番目	3番目
	女1	2	3	1
	女2	2	1	3
	女3	3	2	1
	男1	1	3	2
	男2	2	3	1
	男3	3	1	2

using System;

static class Constants
{
    public const int N = 3;
}

namespace _03_StableMarriageProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            var boy = new int[Constants.N + 1];
            var girl = new int[Constants.N + 1, Constants.N + 1];
            var position = new int[Constants.N + 1];
            var rank = new int[Constants.N + 1, Constants.N + 1];

            int b, g, r, s, t;

            // 女性の好み
            for(g = 1; g <= Constants.N; g++)
            {
                for(r = 1; r <= Constants.N; r++)
                {
                    Console.WriteLine("女性{0}の{1}番目の好みは：",g,r);
                    b = int.Parse(Console.ReadLine());
                    rank[g,b] = r;
                }
                boy[g] = 0;
                rank[g, 0] = Constants.N + 1;
            }

            // 男性の好み
            for(b=1; b <= Constants.N; b++)
            {
                for(r = 1; r <= Constants.N; r++)
                {
                    Console.WriteLine("男性{0}の{1}番目の好みは：", b, r);
                    girl[b,r] = int.Parse(Console.ReadLine());
                    position[b] = 0;
                }
            }

            /* 
             * (1) 男性1は女性1に求婚し、差し当たりOKとする
             * (2) 男性i(>1)が女性iに求婚し、既に男性j(<i)から求婚されていれば女性iは自身の好みに応じて、
             *     求婚されている人物か男性iかを選択する
             * (3) i<Nならばi=i+1として(2)に戻る。そうでなければ終了する
            */
            for(b = 1; b <= Constants.N; b++)
            {
                s = b;
                while(s != 0)
                {
                    g = girl[s, ++position[s]];
                    if (rank[g,s] < rank[g, boy[g]])
                    {
                        t = boy[g];
                        boy[g] = s;
                        s = t;
                    }
                }
            }

            // 出力
            for (g = 1; g <= Constants.N; g++) Console.WriteLine("女:{0}と男:{1}がペア", g, boy[g]);
        }
    }
}

　結果は以下のとおり：

*1:一応補足すると、結婚は一種の比喩でマッチングの問題である。