安定な結婚の問題

/*
 * 出典元「C言語による最新アルゴリズム事典」奥村晴彦著 - P5
 * インデントは変更してあります。
 * 他にも、メッセージや変数名や処理を変更している場合があります。
 */
#include <stdio.h>
#include <stdlib.h>

#define N 3

int boy[N + 1];
int girl[N + 1][N + 1];
int position[N + 1];
int rank[N + 1][N + 1];

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

    for (g = 1; g <= N; g++)
    {
        for (r = 1; r <= N; r++)
        {
            scanf("%d", &b);
            rank[g][b] = r;
        }

        /* sentinels */
        boy[g] = 0;
        rank[g][0] = N + 1;
    }

    for (b = 1; b <= N; b++)
    {
        for (r = 1; r <= N; r++)
        {
            scanf("%d", &g);
            girl[b][r] = g;
        }
        position[b] = 0;
    }

    for (b = 1; b <= 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 <= N; g++)
    {
        printf("Girl %d - Boy %d\n", g, boy[g]);
    }
}

#!/bin/bash

function repeat {
    for i in $(seq $2)
    do
        echo $1
    done
}

function repeat2 {
    for i in $(seq $2)
    do
        for j in $(seq $3)
        do
            echo $1
        done
    done
}

let N=3
let N1=$N+1

boy=( $(repeat 0 $N1) )
girl=( $(repeat2 0 $N1 $N1) )
position=( $(repeat 0 $N1 ))
rank=( $(repeat2 0 $N1 $N1 ))

function index {
    local i=$1
    local j=$2
    local n=$3
    echo $(( $i * $n + $j))
}

function get_girl {
    echo ${girl[$( index $1 $2 $N1 )]}
}

function set_girl {
    girl[$( index $1 $2 $N1 )]=$3
}

function get_rank {
    echo ${rank[$( index $1 $2 $N1 )]}
}

function set_rank {
    rank[$( index $1 $2 $N1 )]=$3
}

for g in $(seq $N)
do
    read -a bs;
    for r in $(seq $N)
    do
        set_rank $g ${bs[$(( $r - 1))]} $r
    done

    # sentinels
    boy[$g]=0
    set_rank $g 0 $N1
done

for b in $(seq $N)
do
    read -a gs
    for r in $(seq $N)
    do
        set_girl $b $r ${gs[$(( $r - 1 ))]}
    done
    position[$b]=0
done


echo ${rank[*]}
echo ${girl[*]}

for b in $(seq $N)
do
    s=$b
    while [ $s -ne 0 ]
    do
        (( ++position[$s] ))
        g=$(get_girl $s ${position[$s]})
        if [ $(get_rank $g $s) -lt $(get_rank $g ${boy[$g]}) ]
        then
            # swap
            t=${boy[$g]}
            boy[$g]=$s
            s=$t
        fi
    done
done

for g in $(seq $N)
do
    printf "Girl %d - Boy %d\n" $g ${boy[$g]}
done

#!/usr/bin/fish

function repeat -a value n
    for i in (seq $n)
        echo $value
    end
end

set N 3

set boy (repeat 0 $N) # result
set girl (repeat 0 (math "$N * $N"))
set position (repeat 0 $N)
set rank (repeat 0 (math "$N * ($N + 1)"))

function index -a i j n
    echo (math "($i - 1) * $n + $j")
end

function get_girl -a b r
    echo $girl[(index $b $r $N)]
end

function set_girl -a b r g
    set -g girl[(index $b $r $N)] $g
end

function get_rank -a g b
    echo $rank[(index $g $b (math $N + 1))]
end

function set_rank -a g b r
    set -g rank[(index $g $b (math $N + 1))] $r
end

# read girls' picks
for g in (seq $N)
    read -a -l bs
    for r in (seq $N)
        set_rank $g $bs[$r] $r
    end

    # sentinels
    set boy[$g] (math $N + 1)
    set_rank $g (math $N + 1) (math $N + 1) 
end

# read boys' picks
for b in (seq $N)
    read -a -l gs
    for r in (seq $N)
        set_girl $b $r $gs[$r]
    end
    set -g position[$b] 0
end

# apply algorithm
for b in (seq $N)
    set -l s $b
    while test $s -ne (math $N + 1)
        set position[$s] (math $position[$s] + 1)
        set -l g (get_girl $s $position[$s])
        if test (get_rank $g $s) -lt (get_rank $g $boy[$g])
            # swap
            set -l t $boy[$g]
            set boy[$g] $s
            set s $t
        end
    end
end

for g in (seq $N)
    printf "Girl %d - Boy %d\n" $g $boy[$g]
end