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 ?

well, it doesnt compile.

you cant do anything regarding debugging until you at least get it to compile

C:\Users\jezebel\Documents>cl marriage.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.21022.08 for 80x86
Copyright (C) Microsoft Corporation.  All rights reserved.

marriage.c
marriage.c(66) : error C2065: 'Man' : undeclared identifier
marriage.c(67) : error C2065: 'Women' : undeclared identifier
marriage.c(67) : error C2146: syntax error : missing ';' before identifier 'engageSet'
marriage.c(67) : warning C4552: '/' : operator has no effect; expected operator with side-effect
marriage.c(95) : error C2065: 'man' : undeclared identifier
marriage.c(95) : error C2146: syntax error : missing ';' before identifier 'mset'

C:\Users\jezebel\Documents>

.

fix the errors and repost your code, then i'll try to run it again and see if it works according to the specs you described.

thank you my friend. i have just message you the code where i fixed the errors.

yeah, i just saw it. for the benefit of others who may have similar problems -- and for the benefit of yourself, in case i give you an incorrect answer -- please do not try to take this thread into the private sphere.

post your updates/comments/questions/remarks/solutions here in this thread.

thanks

i have fixed the mistakes...

#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) {
printf ("\n\nPlease Wait while the Algorithm computes the Stable Set\n\n");
initializeSets();
startStableMatch();
printEngageSet();
return 0;
}

is it normal for you to write your code in this manner? what i mean is, do you intentionally refuse to indent your code, and purposefully line all your brackets up against the left wall?

because you see, im trying to debug your code -- I truly think this in an interesting puzzle -- but damned if it isnt frustrating as all hell to try and read it all smashed up against the left margin.

so rather than thinking about your code, all i can think of is, "why did he do this? do i want to go and insert 100 <tabs> in this guy's program, just so i can read it? ... is this what i want to do with my time?"

already I've spent 15 minutes in frustration plus typing this complaint. If i wasn't intrigued bythe problem i would have just quit looking at it and ignored this thread altogether.

one problem jumps out: if (wset[mset[i].menPreference[mset[i].proposeToW]].free ... your "mset.proposeToW" evaluates to the value 4, and then is used as an index for another arrays with only four elements.

that's a run-time ARRAY OVERFLOW error.


.

@ jephthah :

If you are using Visual studio 200(x) you can let VS do all the hard work of indenting by pressing:

ctrl-a
ctrl-k
ctrl-f

You can even change a setting so that the indention becomes 1 tab, or 4 spaces or 2 spaces or...

Comments
good hint. maybe one day ill get VS
This article has been dead for over six months. Start a new discussion instead.