This problem deals with a group of men and a group of women. The program tries t
ID: 3535182 • Letter: T
Question
This problem deals with a group of men and a group of women. The program tries to pair them up so as to generate as many stable marriages as possible. A set of marriages is unstable if you can find a man and a woman who would rather be married to each other than to their current spouses (in which case the two would be inclined to divorce their spouses and marry each other).
The input file for the program will list all of the men, one per line, followed by a blank line, followed by all of the women, one per line. The men and women are numbered according to their positions in the input file (the first man is #1, the second man #2, and so on; the first woman is #1, the second woman is #2, and so on). Each input line (except for the blank line separating men from women) lists the person's name, followed by a colon, followed by a list of integers. These integers are the marriage partner preferences of this particular person. For example, the following input line is the men's section:
Joe: 10 8 35 9 20 22 33 6 29 7 32 16 18 25
This line indicates that the person is named "Joe" and that his first choices for marriage is woman#10, his second choice is woman #8, and so on. Any women not list are considered unacceptable to Joe.
The stable marriage problem is solved by the following algorithm:
assign each person to be free.
while (some man M with a nonempty preference list is free) {
W=first woman on M's list.
if (some man P is engaged to W) {
assign P to be free.
}
assign M and W to be engaged to each other.
for (each successor Q of M who is on W's list) {
delete W from Q's preference list.
delete Q from W's preference list.
}
}
Consider the following input:
Man 1: 4 1 2 3
Man 2: 2 3 1 4
Man 3: 2 4 3 1
Man 4: 3 1 4 2
Woman 1: 4 1 3 2
Woman 2: 1 3 2 4
Woman 3: 1 2 3 4
Woman 4: 4 1 3 2
The following is a stable marriage solution for this input:
Man 1 and Woman 4
Man 3 and Woman 2
Man 2 and Woman 3
Man 4 and Woman 1
Comments through out is much appreciated but not necessary! Thank you!
Explanation / Answer
In what language, you want the code?
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.