•
•
•
•
What is DaniWeb IT Discussion Community?
You're currently browsing the C section within the Software Development category of DaniWeb, a massive community of 374,004 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 2,741 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our C advertiser:
Views: 624 | Replies: 14
 |
•
•
Join Date: May 2008
Posts: 8
Reputation: 
Rep Power: 0
Solved Threads: 0
Newbie Poster
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 :
any help ?
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 ?
•
•
Join Date: May 2006
Location: ★★ijug.net★★
Posts: 817
Reputation:
Rep Power: 4
Solved Threads: 61
Practically a Posting Shark
Where are you stuck , specify line numbers and problems.
★★ Homework Help ★★ Freelance Programmer ★★ Freelance Jobs ★★
★★ Build A Website ★★ Interview Question And Answer ★★ Tax Filing ★★
★★ Build A Website ★★ Interview Question And Answer ★★ Tax Filing ★★
•
•
Join Date: May 2008
Posts: 8
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
i am not stuck anywhere... i want to know if there are any mistakes..
•
•
Join Date: Feb 2008
Location: Seattle
Posts: 670
Reputation:
Rep Power: 4
Solved Threads: 42
Practically a Master Poster
i can compile it and run it through some tests, if that's what you're looking for?
•
•
Join Date: May 2008
Posts: 8
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
yes jephthah.
and can i have the results please?
and can i have the results please?
•
•
Join Date: Feb 2008
Location: Seattle
Posts: 670
Reputation:
Rep Power: 4
Solved Threads: 42
Practically a Master Poster
i wont be able to get to it tonight, too much to do... tomorrow, though.
•
•
Join Date: Feb 2008
Location: Seattle
Posts: 670
Reputation:
Rep Power: 4
Solved Threads: 42
Practically a Master Poster
well, it doesnt compile.
you cant do anything regarding debugging until you at least get it to 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>
.
Last edited by jephthah : May 8th, 2008 at 4:44 am.
•
•
Join Date: Feb 2008
Location: Seattle
Posts: 670
Reputation:
Rep Power: 4
Solved Threads: 42
Practically a Master Poster
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.
•
•
Join Date: May 2008
Posts: 8
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
thank you my friend. i have just message you the code where i fixed the errors.
•
•
Join Date: Feb 2008
Location: Seattle
Posts: 670
Reputation:
Rep Power: 4
Solved Threads: 42
Practically a Master Poster
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
post your updates/comments/questions/remarks/solutions here in this thread.
thanks
|
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
•
•
•
•
•
•
•
•
DaniWeb C Marketplace
Linear Mode
Similar Threads
- Recursivity (C++)
Other Threads in the C Forum
- Previous Thread: Ranking Array Failure?
- Next Thread: ftell() fclose() and FILE* f = NULL
