In this work you will materialise a algorithm that solves the problem of Stable Marriage. In this problem we aim at "n" men and "n" women and our goal is the contracting of constant marriages between men and women. Obviously each man can be wedded only one woman and one woman one man similarly. Each individual, or man or woman, does not prefer to himself all the individuals of opposite sex but has a order of preference.
All men and the women can very easily shape "n" pairs between them. The problem is how stable are these marriages that are contracted. Be considered that between the wedded pairs, exist two pairs (a,g) and (a',g') where a and a' are men and g and g' women and that also a prefers more the g' from the g and the g' prefers more the a from the a'. It is very likely the a and the g' abandon their couples and become pair. Consequently, the question is finding "n" of pairs between men and women which constitutes viable marriages that is to say there should be no cases as the one that was reported above. The algorithm that it solves the problem of stable marriage is :
Initially all the men and women are free.There is a man "a" which is free and has not made proposal in any of the women.
Choose a such man "a".
Be it "g" the woman who has a higher ranking in the preferences of "a" and in which "a" has still not made proposal.
If the "g" is free then
"a" and "g" becomes pair.
Otherwise if the "g" is already pair with man "a'" then
If the g prefers more the "a'" from the "a" then
the "a" remains free.
Otherwise the g abandons the "a' " and becomes pair with the "a".
the "a" is henceforth free.
End If
End If
End While.
You are called materialise algorithm adopting suitable structures of data. Concretely, the structures that you will use will be supposed to ensure that each repetition of bronchus While requires time O(1), that is to say the crowd of action that is executed in a repetition of is constant independent size of problem "n". Also the structures that you will use will be supposed to occupy space o(n^2) maximum.
Finally, before the beginning of implementation of repetitive bronchus it can precede a phase of arhjkopoj'isis of structures where hrisjmopojsete. The cost in time of this phase should be very o(n^2).
i have done this so far :
#include <stdio.h>
#include <stdlib.h>
// Structure and Global Variables
//-------------------------------------------------
//VARIABLES AND NAMES THAT YOU CAN CHANGE
//Number of Men and Women you need to match
#define MWTOTAL 4
// Add Women and Men names below to match the MWTOTAL
char *wnames[50] = {
"Sarah",
"Michelle",
"Liz",
"Estella"
};
char *mnames[50] = {
"John",
"Travis",
"Don",
"Launnie"
};
//VARIABLES AND NAMES CHANGE ENDS HERE
//--------------------------------------------------
struct women {
int free;
int womenPreference[MWTOTAL];
} wset[MWTOTAL];
struct men {
int free;
int menPreference[MWTOTAL];
int proposeToW;
} mset[MWTOTAL];
int engageSet[MWTOTAL][MWTOTAL];
int totalEngaged=0;
// Function Definitions and Declarations
void initializeSets() {
int i;
for(i=0; i<MWTOTAL; i++) {
mset[i].free = -1; //Initially all men are free to propose to every women
mset[i].proposeToW = 0; //Gives the next free women that a man can propose
wset[i].free = -1;
}
}
void startStableMatch() {
int i,j,k,l,temp,temp1=0,cnt=0;
while (1) {
for (i=0; i<MWTOTAL; i++) {
if (mset[i].free == -1) { // A man is free to propose in decreasing order of preference
if (wset[mset[i].menPreference[mset[i].proposeToW]].free == -1) { //If Women is free, engage the
Man/Women
engageSet[totalEngaged][0] = i;
engageSet[totalEngaged][1] = mset[i].menPreference[mset[i].proposeToW];
totalEngaged++;
wset[mset[i].menPreference[mset[i].proposeToW]].free = 0; //Women is not free anymore
mset[i].free = 0;
mset[i].proposeToW++;
}
else {
for (j=0; j<MWTOTAL; j++) {
if ( i == wset[mset[i].menPreference[mset[i].proposeToW]].womenPreference[j] ) break;
}
for (k=0; k<totalEngaged; k++) {
if ( engageSet[k][1] == mset[i].menPreference[mset[i].proposeToW] ) {
for (l=0; l<MWTOTAL; l++) {
if (engageSet[k][0] == wset[mset[i].menPreference[mset
[i].proposeToW]].womenPreference[l]) {
if ( j < l ) {
temp = engageSet[k][0];
engageSet[k][0] = i; // Women is engaged to the man that just proposed
mset[temp].free = -1; // Free the previously engaged man of W
mset[i].free = 0;
mset[i].proposeToW++;
}
else {
mset[i].free = -1; // Else the Women rejects the man's proposal.. free the
man
mset[i].proposeToW++;
}
break;
}
}
break;
}
}
}
}
}
for (temp1=0; temp1<MWTOTAL; temp1++) {
if (mset[temp1].free == 0) cnt++;
}
if (cnt == 4) break; // No men is free, the algorithm terminates here.
cnt = 0;
}
}
void printEngageSet() {
int i;
printf ("\n\n\tThe stable pairs are listed below\n\n");
printf ("----------------------------------------------------------");
for (i=0; i<totalEngaged; i++) {
printf ("\n\t( %s , %s )\n",mnames[engageSet[i][0]],wnames[engageSet[i][1]]);
}
printf ("----------------------------------------------------------\n\n");
}
int main(void) {
int i;
printf ("\n\nPlease Wait while the Algorithm computes the Stable Set\n\n");
initializeSets();
startStableMatch();
printEngageSet();
return 0;
}any help ?
