Epison07
09-24-2005, 10:54 PM
This is a homework assignment, and I will post the main part of the instructions. I know how you guys feel, as well as most boards on homework, and I am not asking you to complete it for me. I am asking for help. I have already started, but I am stuck, and I suck at recursion. Plus... I dont even think I am truely doing recusion. I am more or less just calling the same function over and over, not really using the return statement like I was taughtin C++... Anywayz
Suppose there are 8 single men and 8 single women. A set of 8 couples formed by marrying these men and women is called an assignment. Obviously, there are many possible assignments. We will be interested in only those assignments that are stable. An assignment is said to be unstable if there exist a man and a woman who are not married to each other but who would both prefer each other to their marriage partners. If no such pair exists in an assignment, the assignment is stable.
The "rules" for this are a little vague, but yeah. Our teacher told us it would be easier to use recursion, so I am trying, but its nto working very well.
And there is also this part of teh instructions that I am not sure how I am going to do, even if I get the main part working.
Write a Java program that uses the file PREF.TXT to generate all stable assignments. Appropriately display <bold>all</bold> the stable assignments on the screen. For example, an assignment (8 couples) can be shown as
Anywayz, here is my code so far. I have a decent amount of comments so it shouldnt be that hard to follow.
import java.util.Scanner;
import java.io.*;
public class dsp2 {
static int [][] man=new int[8][8], woman=new int[8][8];
//men's and women's preferences
//man[a][b] = c
//a = man
//b = mans preference to woman, 0 is most wanted
//c = woman
//same for woman[a][b] = c
static int [] mcouple=new int[8], wcouple=new int[8];
//mcouple[a] = b
//a == man
//b = woman he is married to
//same for wcouple[a] = b
//static boolean married(int w)
// return true if a given woman w is married; false otherwise.
static boolean stable(int m, int w){ //returns true is marriage is stable
int wpref = -1;
for(int x = 0;x<8;x++){ //find womans preference for the to be married man
if(woman[w][x] == m)
wpref = x;
}
for(int x = 0;x<m;x++){
for(int i = 0;i<8;i++){ //comparing her preference to every married guy
if(x == woman[w][i] && i<wpref){
return false;
}
}
}
return true;
}
//static void print_assignment()
//print the array mcouple in appropriate format
static void initializations() throws IOException
{
Scanner inf = new Scanner(new File("pref.txt"));
for(int x = 0;x<8;x++){ //reads information from file
for(int i = 0;i<8;i++){
man[x][i] = inf.nextInt();
}
}
for(int x = 0;x<8;x++){
for(int i = 0;i<8;i++){
woman[x][i] = inf.nextInt();
}
}
for(int x = 0;x<8;x++){ //sets all couples to -1
mcouple[x] = -1;
}
for(int x = 0;x<8;x++){
wcouple[x] = -1;
}
inf.close();
}
static void try_to_marry(int m){
int mwoman; //woman current man wants to marry
if(m == 8) {return;} //checks if all men are married
else if(mcouple[m] == -1){ //finds an unmarried man
for(int x = 0;x<8;x++){ //checks each woman in order man prefers her, if she isnt married
mwoman = man[m][x]; //then we checks if they can be stablely married
if(wcouple[mwoman] == -1){
if(stable(m, mwoman)){
mcouple[m] = mwoman;
wcouple[mwoman] = m;
try_to_marry(m++); //if marrage is stable, call function again
} //for next unmarried man
}
}
}
try_to_marry(m--); //else go back a step
}
public static void main(String[] args) throws IOException
{ System.out.print("program execution begins\n");
initializations();
try_to_marry(0);
Scanner kb=new Scanner(System.in);
String op;
op=kb.next();
}
}
It compiles fine right now, but I get a runtime error. It closes the window itself, so I had to take a screenie to see what ti was saying. And it says there an error in my try_to_marry() function. I think it has to do with the way I call the function in itself, but I dont really have a way to handle returning unless it finds a correct solution for all men. I am a little lost as how to go on.
I really need help, becuz this recursion project is owning me. I really appreciate everyone for reading thro my code and trying to help me solve my problem. Thanks in advance.
-Ep
Suppose there are 8 single men and 8 single women. A set of 8 couples formed by marrying these men and women is called an assignment. Obviously, there are many possible assignments. We will be interested in only those assignments that are stable. An assignment is said to be unstable if there exist a man and a woman who are not married to each other but who would both prefer each other to their marriage partners. If no such pair exists in an assignment, the assignment is stable.
The "rules" for this are a little vague, but yeah. Our teacher told us it would be easier to use recursion, so I am trying, but its nto working very well.
And there is also this part of teh instructions that I am not sure how I am going to do, even if I get the main part working.
Write a Java program that uses the file PREF.TXT to generate all stable assignments. Appropriately display <bold>all</bold> the stable assignments on the screen. For example, an assignment (8 couples) can be shown as
Anywayz, here is my code so far. I have a decent amount of comments so it shouldnt be that hard to follow.
import java.util.Scanner;
import java.io.*;
public class dsp2 {
static int [][] man=new int[8][8], woman=new int[8][8];
//men's and women's preferences
//man[a][b] = c
//a = man
//b = mans preference to woman, 0 is most wanted
//c = woman
//same for woman[a][b] = c
static int [] mcouple=new int[8], wcouple=new int[8];
//mcouple[a] = b
//a == man
//b = woman he is married to
//same for wcouple[a] = b
//static boolean married(int w)
// return true if a given woman w is married; false otherwise.
static boolean stable(int m, int w){ //returns true is marriage is stable
int wpref = -1;
for(int x = 0;x<8;x++){ //find womans preference for the to be married man
if(woman[w][x] == m)
wpref = x;
}
for(int x = 0;x<m;x++){
for(int i = 0;i<8;i++){ //comparing her preference to every married guy
if(x == woman[w][i] && i<wpref){
return false;
}
}
}
return true;
}
//static void print_assignment()
//print the array mcouple in appropriate format
static void initializations() throws IOException
{
Scanner inf = new Scanner(new File("pref.txt"));
for(int x = 0;x<8;x++){ //reads information from file
for(int i = 0;i<8;i++){
man[x][i] = inf.nextInt();
}
}
for(int x = 0;x<8;x++){
for(int i = 0;i<8;i++){
woman[x][i] = inf.nextInt();
}
}
for(int x = 0;x<8;x++){ //sets all couples to -1
mcouple[x] = -1;
}
for(int x = 0;x<8;x++){
wcouple[x] = -1;
}
inf.close();
}
static void try_to_marry(int m){
int mwoman; //woman current man wants to marry
if(m == 8) {return;} //checks if all men are married
else if(mcouple[m] == -1){ //finds an unmarried man
for(int x = 0;x<8;x++){ //checks each woman in order man prefers her, if she isnt married
mwoman = man[m][x]; //then we checks if they can be stablely married
if(wcouple[mwoman] == -1){
if(stable(m, mwoman)){
mcouple[m] = mwoman;
wcouple[mwoman] = m;
try_to_marry(m++); //if marrage is stable, call function again
} //for next unmarried man
}
}
}
try_to_marry(m--); //else go back a step
}
public static void main(String[] args) throws IOException
{ System.out.print("program execution begins\n");
initializations();
try_to_marry(0);
Scanner kb=new Scanner(System.in);
String op;
op=kb.next();
}
}
It compiles fine right now, but I get a runtime error. It closes the window itself, so I had to take a screenie to see what ti was saying. And it says there an error in my try_to_marry() function. I think it has to do with the way I call the function in itself, but I dont really have a way to handle returning unless it finds a correct solution for all men. I am a little lost as how to go on.
I really need help, becuz this recursion project is owning me. I really appreciate everyone for reading thro my code and trying to help me solve my problem. Thanks in advance.
-Ep