安定マッチング for PHP

• php >= 5.4

GSMatch.php

<?php

$boysPrefers = [
 'b1' => [ 'g1','g2','g3','g4' ],
 'b2' => [ 'g3','g2','g1','g4' ],
 'b3' => [ 'g1','g2','g4','g3' ],
 'b4' => [ 'g3','g1','g4','g2' ],
];

$girlsPrefers = [
 'g1' => [ 'b1','b2','b3','b4' ],
 'g2' => [ 'b2','b1','b4','b3' ],
 'g3' => [ 'b2','b3','b1','b4' ],
 'g4' => [ 'b1','b4','b3','b2' ],
];

/**
 * 入力：n人の男性とk人の女性、および、各人の異性全員に対する選好順序のリスト
 * 出力：安定マッチング（つまり、男女 min{n,k} 組以下のペア）
 * 
 * @see https://ja.wikipedia.org/wiki/安定結婚問題
 * @param array $boysPrefers
 * @param array $girlsPrefers
 * @return array 
 */
function GSMatch($boysPrefers, $girlsPrefers) {

    // ステップ 0 [初期設定] 全員の状態は独身とする（全ての男性はどの女性にもプロポーズを行っていない）。
    $pairs = [];
    $boys = array_keys($boysPrefers);
    $girls = array_keys($girlsPrefers);

    // ステップ 1　独身の男性 h が存在する限り、以下の操作を繰り返す。
    while(!empty($boys)) {

        // 1-1 男性 h はまだプロポーズしていない女性の中で、最も好きな（つまり、希望リストの最高位の）相手女性 d にプロポーズする
        $boy = array_shift($boys);
        $girl = array_shift($boysPrefers[$boy]);

        // 1-2 (a) d が独身ならば、d は h と婚約する
        if(empty($pairs[$girl])) {
            $pairs[$girl] = $boy;
        } else {
            // (b) d がすでに h' と婚約している場合
            $girlsFlip = array_flip($girlsPrefers[$girl]);

            // (b-1) d にとって h' のほうが好ましい希望順位が上( h' > h ) ならば、h からのプロポーズを断る
            if($girlsFlip[$pairs[$girl]] < $girlsFlip[$boy]) {
                $boys[] = $boy;
            } else {
                // (b-2) d にとって h のほうが好ましい( h > h' )ならば、h' との婚約を解消し h と婚約する
                $boys[] = $pairs[$girl];
                unset($pairs[$girl]);
                $pairs[$girl] = $boy;
            }
        }
    }

    // ステップ 2　現在婚約しているペアの集合を安定マッチングとして出力する。（終了）
    // 男性最良安定マッチング
    return array_flip($pairs);
}

$result = GSMatch($boysPrefers, $girlsPrefers);
var_dump($result);