The algorithm, expressed as a function stabilitycheck, is implemented in the following program. The program first inputs n. Next it reads in mpairs, creates wpairs from it, reads in mpref and wpref, then creates mpriority and wpriority, calls stabilitycheck to check the pairings, and finally prints the result along with the pairings.
#include <stdio.h>
#define MAXN 50
typedef int pairings[MAXN];
mate(person,pairs)
/* Returns person's mate
as specified by pairs.
*/
int person;
pairings pairs;
{
return(pairs[person]);
}
read_mens_mates(n,pairs)
/* Reads the n mates of the
men into pairs.
*/
int n;
pairings pairs;
{
int i;
printf("\n mpairs = ? \n");
for(i=1;i<=n;i++)
scanf("%d",&pairs[i]);
}
create_womens_mates(n,pairs1,pairs2)
/* Creates in pairs2 the women's mates
based on the men's mates as specified
by pairs1.
*/
int n;
pairings pairs1,pairs2;
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;pairs1[j] != i;j++)
{
}
pairs2[i] = j;
}
}
typedef int preferences[MAXN] [MAXN];
mostpreferred(person,pref)
/* Returns the mate most
preferred by person as
specified by pref.
*/
int person;
preferences pref;
{
return(pref[person][1]);
}
nextpreferred(person,index,pref)
/* Returns the mate next most
preferred by person as specified
by pref.
*/
int person,index;
preferences pref;
{
return (pref[person][index]);
}
prefers(individual,person, individualsmate,priority)
/* Returns true only if individual prefers person
to the individual's mate as specified by priority.
*/
int individual,person,individualsmate;
preferences priority;
{
return(priority[individual][person]
< priority[individual][individualsmate]);
}
read_preferences(n,pref)
/* Reads n rows of
preferences into pref.
*/
int n;
preferences pref;
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&pref[i][j]);
}
create_priorities(n,pref,priority)
/* Creates n individual priorities in
priority based on the individual
preferences specified by pref.
*/
int n;
preferences pref,priority;
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
priority[i][pref[i][j]] = j;
}
#define TRUE 1
#define FALSE 0
main()
{
pairings mpairs,wpairs;
preferences mpref,wpref,mpriority,wpriority;
int i,j,n;
printf("\n n=?\n);
scanf("%d",&n);
read_mens_mates(n,mpairs);
create_womens_mates(n,mpairs,wpairs);
printf("\n Enter mens preferences \n");
read_preferences (n,mpref);
printf("\n Enter womens
preferences \n");
read_preferences (n,wpref);
create_priorities(n,mpref,mpriority);
create_priorities(n,wpref,wpriority);
if(stabilitycheck(n,mpairs,wpairs,mpref,wpref,
mpriority,wpriority))
printf("The pairings are stable \n");
else
printf("The pairings are not stable \n");
printf("The pairings are: \n");
printf("man wife \n");
for(i=1;i<=n;i++)
printf("%d %d \n",i,mate(i,mpairs));
}
stabilitycheck(n,mpairs,wpairs,mpref,wpref,mpriority,wpriority)
/* Checks the entire pairing specified by
the parameters and returns true only
if it is stable.
*/
int n;
pairings mpairs,wpairs;
preferences mpref,wpref,mpriority,wpriority;
{
int man,wife,individual,individualsmate,index,stable;
stable = TRUE;
for(man=1;(stable && man<=n);man++)
{
wife = mate(man,mpairs);
individual = mostpreferred(man,mpref);
index = 1;
while(stable &&(individual != wife))
{
individualsmate = mate(individual,
wpairs);
if(prefers(individual,man,
individualsmate,wpriority))
stable = FALSE;
else
{
index++;
individual = nextpreferred(man,
index,mpref);
}
}
individual = mostpreferred(wife,wpref);
index = 1;
while(stable &&(individual != man))
{
individualsmate = mate(individual,
mpairs);
if(prefers(individual,wife,
individualsmate,mpriority))
stable = FALSE;
else
{
index++;
individual = nextpreferred(wife,
index,wpref);
}
}
}
return(stable);
}