安定結婚問題練習

marrige.c

#include <stdio.h>
#include <stdlib.h>
#define N  3  /* 各性の人数 */

int
  /* 添字(女性1..3) => 値(男性1..3) */
  boy[4] = {0, 0, 0, 0}

  /* 各女性の好み */
  // rank[女性1..3][男性1..3] = ランク
  // 女性3 -> 男性1:1位 男性2:3位 男性3:2位
  , rank[4][4] = {{}, {4, 1, 2, 3}, {4, 3, 2, 1}, {4, 1, 3, 2}}

  /* 各男性の好み */
  // girl[男性1..3][ランク] = 女性1..3
  // 男性1 -> 女性1:2位 女性2:3位 女性3:1位
  , girl[4][4] = {{}, {4, 3, 1, 2}, {4, 2, 3, 1}, {4, 3, 2, 1}}

  , position[4] = {0, 0, 0, 0};

int main(void)
{
    int b, g, r, s, t;

    for (b = 1; b <= N; b++) {
        // b,sは男1..3の値
        s = b;

        while (s != 0) {
            // 男性の好みの女性をランクが上の 女性1..3 を取得
            // 男性単位で2週目以降は次のランクの 女性1..3
            g = girl[s][++position[s]];

            // "女性に対しての男性のランク"
            // と
            // "女性に対しての男性の暫定ランク(暫定ランクがない場合は初期値4になる)"
            // を比較する
            // -----
            // 男性の暫定ランクではない場合は既出の 女性1..3 => 男性1..3 のペア つまり好みが被っている
            // 暫定ランクよりも今回のランクの方が上位の場合は上書き処理に入る
            if (rank[g][s] < rank[g][boy[g]]) {
                // 暫定ペアを一時保存(暫定ペアがない場合は初期値4になる)
                t = boy[g];

                // 暫定で 女性1..3 => 男性1..3 を保存
                boy[g] = s;

                // 次に処理する男性1..3
                // 暫定ランクよりも上位だった場合はもう一度その男性でペアを保存しに行く
                s = t;
            }
        }
    }
    for (g = 1; g <= N; g++) {
        printf("女 %d - 男 %d\n", g, boy[g]);
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define N  3  /* 各性の人数 */

int
  /* 添字(女性1..3) => 値(男性1..3) */
  boy[4] = {0, 0, 0, 0}

  /* 各女性の好み */
  // rank[女性1..3][男性1..3] = ランク
  // 女性3 -> 男性1:1位 男性2:3位 男性3:2位
  , rank[4][4] = {{}, {4, 1, 2, 3}, {4, 3, 2, 1}, {4, 1, 3, 2}}

  /* 各男性の好み */
  // girl[男性1..3][ランク] = 女性1..3
  // 男性1 -> 女性1:2位 女性2:3位 女性3:1位
  , girl[4][4] = {{}, {4, 3, 1, 2}, {4, 2, 3, 1}, {4, 3, 2, 1}}

  , position[4] = {0, 0, 0, 0};

int main(void)
{
    int b, g, r, s, t;

    for (b = 1; b <= N; b++) {
        s = b;
        while (s != 0) {
            // 1-1週目 男性1のランク1 -> g = 女性3
            // 2-1週目 男性2のランク1 -> g = 女性2
            // 3-1週目 男性3のランク1 -> g = 女性3
            // 3-2週目 男性3のランク2 -> g = 女性2
            // 3-3週目 男性2のランク2 -> g = 女性3
            // 3-4週目 男性2のランク3 -> g = 女性1
            g = girl[s][++position[s]];

            // 1-1週目 (女性3の男性1のランク=1) < (女性3の男性0のランク=4(番人))
            // 2-1週目 (女性2の男性2のランク=2) < (女性2の男性0のランク=4(番人))
            // 3-1週目 (女性3の男性3のランク=2) < (女性3の男性3のランク=1)
            // 3-2週目 (女性2の男性3のランク=1) < (女性2の男性3のランク=2)
            // 3-3週目 (女性3の男性2のランク=2) < (女性3の男性2のランク=2)
            // 3-4週目 (女性1の男性2のランク=1) < (女性1の男性0のランク=4(番人))
            if (rank[g][s] < rank[g][boy[g]]) {
                // 1-1週目 t = 0
                // 2-1週目 t = 0
                // 3-2週目 t = 2
                // 3-4週目 t = 0
                t = boy[g];
                // 1-1週目 boy[3]に1 {0, 0, 0, 1}
                // 2-1週目 boy[2]に2 {0, 0, 2, 1}
                // 3-2週目 boy[2]に3 {0, 0, 3, 1}
                // 3-4週目 boy[1]に2 {0, 2, 3, 1}
                boy[g] = s;
                // 1-1週目 s = 0
                // 2-1週目 s = 0
                // 3-3週目 s = 2
                // 3-3週目 s = 0
                s = t;
            }
        }
    }
    for (g = 1; g <= N; g++) {
        printf("女 %d - 男 %d\n", g, boy[g]);
    }
    return 0;
}