ここでは2つのグループ(男、女)があり、お互いのグループの各メンバーは異なるグループのメンバーとカップルとなることを望んでおり、それぞれ異なるグループのメンバーについて、カップルとなりたい順序を持っているとする。 また誰ともカップルとならなかったら、最悪だと考えている。 さらにここでは簡単化のため、カップルの申し込みはグループ1のメンバーのみとする。
GSアルゴリズムの手順:
1. グループ1のメンバーはグループ2の第1希望のメンバーに一斉にカップルの申し込みを行う。
2. グループ2のメンバーは自分の好みにいちばん近い人を選んでキープし、残りのメンバーを拒否する
3. グループ1のメンバーは拒否される度に次に好みのメンバーに申し込む。
4. グループ2のメンバーはより好みのグループ1のメンバーの申し込みが来るたびにキープ相手を変更し、残りを断る。
※この作業を断られるグループ1のメンバーがいなくなるまで続ける。
/*
* Stable Matching Algorithm
* Gale-Shapley Algorithm
*/
#include ＜stdio.h>
#include ＜stdlib.h>
#include ＜time.h>
/* prefrence value is stronger as value is small ( 0 is most prefered ) */
#define NUMBER 10
void set_random( int* );
void initialize( int **, int **, int *, int *, int * );
int main( int argc, char **argv )
{
int i, j;
/* NUMBER is invalid(initial) NUMBER */
int *men_pref[ NUMBER ],
*women_pref[ NUMBER ]; /* preference list of women */
int prop_list[ NUMBER ];
int marriage_men[ NUMBER ];
int marriage_women[ NUMBER ];
initialize( men_pref, women_pref, prop_list, marriage_men, marriage_women );
for( j = 0; j ＜ NUMBER; j++ ) {
printf( "MAN[%d]: ", j );
for( i = 0; i ＜ NUMBER; i++ )
printf( "%d, ", men_pref[ j ][ i ] );
printf( "\tWOMAN[%d]: ", j );
for( i = 0; i ＜ NUMBER; i++ )
printf( "%d, ", women_pref[ j ][ i ] );
printf("\n");
}
for( j = 0; j ＜ NUMBER; j++ ) {
printf( "== trial %d ==\n", j );
trial( men_pref, women_pref, prop_list, marriage_men, marriage_women );
printf("MEN: ");
for( i = 0; i ＜ NUMBER; i++ ) {
printf( "%2d ", marriage_men[ i ] );
}
printf( "\nWOMEN: " );
for( i = 0; i ＜ NUMBER; i++ ) {
printf( "%2d ", marriage_women[ i ] );
}
printf( "\n" );
}
for( i = 0; i ＜ NUMBER; i++ ) {
free( men_pref[ i ] );
free( women_pref[ i ] );
}
return 0;
}
int trial( int *men_list[], int *women_list[], int *prop_list, int *marriage_men, int *marriage_women )
{
int i, j;
int man_index, woman_index;
for( i = 0; i ＜ NUMBER; i++ ) {
if( marriage_men[ i ] != NUMBER ) { // already married
continue;
}
woman_index = men_list[ i ][ prop_list [ i ] ];
if( marriage_women[ woman_index ] == NUMBER ) { // woman is free
marriage_men[ i ] = woman_index; // marriage
marriage_women[ woman_index ] = i; // marriage
} else {
man_index = marriage_women[ woman_index ]; // man married targeted woman
for( j = 0; j ＜ NUMBER; j++ ) {
if( women_list[ woman_index ][ j ] == man_index ) // marriaged man is prefered
break;
else if( women_list[ woman_index ][ j ] == i ) { // proposed man is prefered
marriage_men[ i ] = woman_index; // marriage
marriage_women[ woman_index ] = i; // marriage
marriage_men[ man_index ] = NUMBER; // dismarriage
}
}
}
prop_list[ i ] ++;
}
return 0;
}
void set_random( int *list )
{
int i, tmp;
for( i = 0; i ＜ NUMBER; i++ ){
list[i] = NUMBER;
}
for( i = 0; i ＜ NUMBER; i++ ){
while( list[( tmp = random( ) % NUMBER )] != NUMBER ); /* retry */
list[tmp] = i; /* set preference value */
}
return;
}
void initialize( int *men_list[], int *women_list[], int *prop_list, int *marriage_men, int *marriage_women )
{
int i, tmp;
srandom( time( 0 ) );
for( i = 0; i ＜ NUMBER; i++ ) {
if( ( men_list[ i ] = (int *)malloc( NUMBER * sizeof( int ) ) ) == NULL ) {
perror( "malloc" );
exit( EXIT_FAILURE );
}
set_random( men_list[ i ] );
if( ( women_list[ i ] = (int *)malloc( NUMBER * sizeof( int ) ) ) == NULL ) {
perror( "malloc" );
exit( EXIT_FAILURE );
}
set_random( women_list[ i ] );
prop_list[ i ] = 0;
marriage_men[ i ] = NUMBER;
marriage_women[ i ] = NUMBER;
}
return;
}
出力結果
MAN[0]: 2, 3, 8, 0, 4, 9, 1, 7, 5, 6, WOMAN[0]: 8, 3, 4, 7, 6, 0, 9, 1, 2, 5, MAN[1]: 9, 0, 6, 3, 5, 8, 7, 2, 1, 4, WOMAN[1]: 2, 5, 0, 8, 4, 3, 7, 1, 6, 9, MAN[2]: 1, 7, 6, 3, 0, 4, 2, 8, 9, 5, WOMAN[2]: 2, 9, 3, 5, 0, 4, 8, 1, 7, 6, MAN[3]: 6, 5, 2, 9, 1, 7, 8, 4, 0, 3, WOMAN[3]: 8, 4, 5, 7, 3, 6, 9, 2, 0, 1, MAN[4]: 6, 2, 5, 9, 0, 1, 7, 4, 3, 8, WOMAN[4]: 5, 4, 8, 3, 1, 9, 2, 0, 6, 7, MAN[5]: 9, 0, 2, 1, 3, 5, 4, 7, 8, 6, WOMAN[5]: 7, 5, 8, 0, 6, 1, 2, 9, 4, 3, MAN[6]: 5, 1, 3, 8, 6, 4, 7, 0, 9, 2, WOMAN[6]: 1, 3, 0, 4, 5, 7, 9, 6, 2, 8, MAN[7]: 7, 9, 4, 8, 3, 2, 5, 1, 0, 6, WOMAN[7]: 9, 2, 0, 3, 4, 1, 6, 5, 8, 7, MAN[8]: 2, 4, 1, 6, 3, 5, 9, 0, 8, 7, WOMAN[8]: 6, 4, 1, 8, 7, 5, 3, 0, 9, 2, MAN[9]: 8, 0, 2, 5, 4, 3, 9, 1, 7, 6, WOMAN[9]: 3, 2, 6, 4, 1, 7, 9, 0, 8, 5, == trial 0 == MEN: 2 9 1 6 10 10 5 7 10 8 WOMEN: 10 2 0 10 10 6 3 7 9 1 == trial 1 == MEN: 2 9 1 6 10 0 5 7 4 8 WOMEN: 5 2 0 10 8 6 3 7 9 1 == trial 2 == MEN: 2 9 1 6 10 0 5 7 4 8 WOMEN: 5 2 0 10 8 6 3 7 9 1 == trial 3 == MEN: 2 10 1 6 9 0 5 7 4 8 WOMEN: 5 2 0 10 8 6 3 7 9 4 == trial 4 == MEN: 10 0 1 6 9 2 5 7 4 8 WOMEN: 1 2 5 10 8 6 3 7 9 4 == trial 5 == MEN: 3 0 1 6 9 2 5 7 4 8 WOMEN: 1 2 5 0 8 6 3 7 9 4 == trial 6 == MEN: 3 0 1 6 9 2 5 7 4 8 WOMEN: 1 2 5 0 8 6 3 7 9 4 == trial 7 == MEN: 3 0 1 6 9 2 5 7 4 8 WOMEN: 1 2 5 0 8 6 3 7 9 4 == trial 8 == MEN: 3 0 1 6 9 2 5 7 4 8 WOMEN: 1 2 5 0 8 6 3 7 9 4 == trial 9 == MEN: 3 0 1 6 9 2 5 7 4 8 WOMEN: 1 2 5 0 8 6 3 7 9 4
#include ＜stdio.h>
int verbose = 0;
enum {
clown = -1,
abe, bob, col, dan, ed, fred, gav, hal, ian, jon,
abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan,
};
const char *name[] = {
"Abe", "Bob", "Col", "Dan", "Ed", "Fred", "Gav", "Hal", "Ian", "Jon",
"Abi", "Bea", "Cath", "Dee", "Eve", "Fay", "Gay", "Hope", "Ivy", "Jan"
};
int pref[jan + 1][jon + 1] = {
{ abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay },
{ cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay },
{ hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan },
{ ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi },
{ jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay },
{ bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay },
{ gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay },
{ abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee },
{ hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve },
{ abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope },
{ bob, fred, jon, gav, ian, abe, dan, ed, col, hal },
{ bob, abe, col, fred, gav, dan, ian, ed, jon, hal },
{ fred, bob, ed, gav, hal, col, ian, abe, dan, jon },
{ fred, jon, col, abe, ian, hal, gav, dan, bob, ed },
{ jon, hal, fred, dan, abe, gav, col, ed, ian, bob },
{ bob, abe, ed, ian, jon, dan, fred, gav, col, hal },
{ jon, gav, hal, fred, bob, abe, col, ed, dan, ian },
{ gav, jon, bob, abe, ian, dan, hal, ed, col, fred },
{ ian, col, hal, gav, fred, bob, abe, ed, jon, dan },
{ ed, hal, gav, abe, bob, jon, col, ian, fred, dan },
};
int pairs[jan + 1], proposed[jan + 1];
void engage(int man, int woman)
{
pairs[man] = woman;
pairs[woman] = man;
if (verbose) printf("%4s is engaged to %4s\n", name[man], name[woman]);
}
void dump(int woman, int man)
{
pairs[man] = pairs[woman] = clown;
if (verbose) printf("%4s dumps %4s\n", name[woman], name[man]);
}
/* how high this person ranks that: lower is more preferred */
int rank(int this, int that)
{
int i;
for (i = abe; i ＜= jon && pref[this][i] != that; i++);
return i;
}
void propose(int man, int woman)
{
int fiance = pairs[woman];
if (verbose) printf("%4s proposes to %4s\n", name[man], name[woman]);
if (fiance == clown) {
engage(man, woman);
} else if (rank(woman, man) ＜ rank(woman, fiance)) {
dump(woman, fiance);
engage(man, woman);
}
}
int covet(int man1, int wife2)
{
if (rank(man1, wife2) ＜ rank(man1, pairs[man1]) &&
rank(wife2, man1) ＜ rank(wife2, pairs[wife2])) {
printf( " %4s (w/ %4s) and %4s (w/ %4s) prefer each other"
" over current pairing.\n",
name[man1], name[pairs[man1]], name[wife2], name[pairs[wife2]]
);
return 1;
}
return 0;
}
int thy_neighbors_wife(int man1, int man2)
{ /* +: force checking all pairs; "||" would shortcircuit */
return covet(man1, pairs[man2]) + covet(man2, pairs[man1]);
}
int unstable()
{
int i, j, bad = 0;
for (i = abe; i ＜ jon; i++) {
for (j = i + 1; j ＜= jon; j++)
if (thy_neighbors_wife(i, j)) bad = 1;
}
return bad;
}
int main()
{
int i, unengaged;
/* init: everyone marries the clown */
for (i = abe; i ＜= jan; i++)
pairs[i] = proposed[i] = clown;
/* rounds */
do {
unengaged = 0;
for (i = abe; i ＜= jon; i++) {
//for (i = abi; i ＜= jan; i++) { /* could let women propose */
if (pairs[i] != clown) continue;
unengaged = 1;
propose(i, pref[i][++proposed[i]]);
}
} while (unengaged);
printf("Pairing:\n");
for (i = abe; i ＜= jon; i++)
printf(" %4s - %s\n", name[i],
pairs[i] == clown ? "clown" : name[pairs[i]]);
printf(unstable()
? "Marriages not stable\n" /* draw sad face here */
: "Stable matchup\n");
printf("\nBut if Bob and Fred were to swap:\n");
i = pairs[bob];
engage(bob, pairs[fred]);
engage(fred, i);
printf(unstable() ? "Marriages not stable\n" : "Stable matchup\n");
return 0;
}
出力結果
Pairing:
Abe - Ivy
Bob - Cath
Col - Dee
Dan - Fay
Ed - Jan
Fred - Bea
Gav - Gay
Hal - Eve
Ian - Hope
Jon - Abi
Stable matchup
But if Bob and Fred were to swap:
Fred (w/ Cath) and Ivy (w/ Abe) prefer each other over current pairing.
Bob (w/ Bea) and Fay (w/ Dan) prefer each other over current pairing.
Bob (w/ Bea) and Hope (w/ Ian) prefer each other over current pairing.
Bob (w/ Bea) and Abi (w/ Jon) prefer each other over current pairing.
Fred (w/ Cath) and Dee (w/ Col) prefer each other over current pairing.
Fred (w/ Cath) and Abi (w/ Jon) prefer each other over current pairing.
Marriages not stable
