aspose file tools*
The moose likes Beginning Java and the fly likes Stable Marriage Problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Stable Marriage Problem" Watch "Stable Marriage Problem" New topic
Author

Stable Marriage Problem

Dave DiRito
Ranch Hand

Joined: Feb 08, 2008
Posts: 77
Need to solve the classic marriage problem with a group of 4 men and 4 women. This is in a chapter on ArrayLists, LinkedLists, Sets, and Maps, so I assume some combination of these would be used in the solution. The pseudocode that is provided in the text is as follows:

Here is the code I've built so far. Now, I'm wondering how to fit this stuff into the loop. For instance, how do I loop through each of the ArrayLists and maps to tell if "some man M with a nonempty preference list is free"? Am I on the right track at all with this?

marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

Maybe I'm thinking too much, but I would approach this by modeling the situation a little more accurately. Specifically, I think I would define a Man class and a Woman class where each HAS-A preferenceList and HAS-A status ("free" or "engaged").

It looks like the preference lists are initialized based on some data you've been provided in an array called "prefs." But the way you're pulling from this array, manX and womanX will have identical preference lists (i.e., the same order of numbers, just representing the opposite gender). Is this correct?

After these pieces are in place, I would then frame the logic for the algorithm, paralleling the pseudocode as closely as possible.

I would also suggest writing lots of descriptive println statements into the logic, so that you can "see inside" the method as its running. Otherwise, this could be very difficult to debug if you just get some final output that doesn't make sense.
[ April 10, 2008: Message edited by: marc weber ]

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Dave DiRito
Ranch Hand

Joined: Feb 08, 2008
Posts: 77
Thanks for the suggestions, Mark. I am building the array from a data file that is provided and the array represents the data correctly when I print it out. Each man and woman has different preferences.

I'll see if I can go forward with your suggestions.

Dave
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

Is there any more to the pseudocode?
Dave DiRito
Ranch Hand

Joined: Feb 08, 2008
Posts: 77
No, that's all that was provided in the text for this problem. It's from the book "Building Java Programs" by Stuart Reges and Marty Stepp. Are you familiar with that text?
Dave DiRito
Ranch Hand

Joined: Feb 08, 2008
Posts: 77
The data file of preferences looks like this:

4 1 2 3
2 3 1 4
2 4 3 1
3 1 4 2

4 1 3 2
1 3 2 4
1 2 3 4
4 1 3 2

The first 4 rows are the men's preferences and the woman's preferences come after the blank line. The first man has preferences 4 1 2 3.

I decided to read them into a two dimensional array on my own. My thinking was that it would be an easy way to keep track of and get to everyone's preferences and I could easily pass the whole thing into a method that way. I can tell whether the preferences are a man's or a woman's as well as which particular man or woman's it is by the location in the array.

I'm still wondering if that's a good idea or not.
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

The array should work fine. But then the women should use prefs[4], [5], [6], and [7], instead of starting over with 0 and using the same preferences as the men.

(I'm not familiar with the book.)
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Stable Marriage Problem