Introduction
代写一个小算法，在给定的好感度下，求最优的男女匹配算法。所谓最优就是配对男女的最大化。
Requirement
You are going to write a program that solves a classic computer science problem known as the stable marriage problem. The input file is divided into men and women and the program tries to pair them up so as to generate as many marriages as possible that are all stable. 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 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 an input line with just the word “END” on it, followed by all of the women, one per line, followed by another input line with just the word “END” on it. The men and women are numbered by their position in the input file. To make this easier, we have numbered starting at O (the first man is #0, the second man is #1, and so on; the first woman is #0, the second woman is #1, and so on). Each input line (except the two lines with “END”) has a name followed by a colon followed by a list of integers. The integers are the preferences for this particular person. For example, the following input line in the men’s section:
Joe: 9 7 34 8 19 21 32 5 28 6 31 15 17 24
indicates that the person is named “Joe” and that his first choice for marriage is woman #9, his second choice is woman #7, and so on. Any women not listed are considered unacceptable to Joe. The data file has been purged of any impossible pairings where one person is interested in the other, but the other considers that person unacceptable. Thus, if a woman appears on Joe’s list, then Joe is acceptable to that woman.
There are many ways to approach the stable marriage problem. You are to implement a specific algorithm described below. This is the basic outline:
set 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) {
set p to be free
}
set m and w to be engaged to each other
for (each successor q of m on w's list) {
delete w from q's preference list
delete q from w's preference list
}
}
Consider, for example, the following short input:
Man 0: 3 0 1 2 Woman 0: 3 0 2 1
Man 1: 1 2 0 3 Woman 1: 0 2 1 3
Man 2: 1 3 2 0 Woman 2: 0 1 2 3
Man 3: 2 0 3 1 Woman 3: 3 0 2 1
It doesn’t matter where we start, so suppose we start with man 0. We engage him to woman 3 (the first choice on his list). Men 2 and 1 appear after man 0 in woman 3’s list. Thus, we delete those connections.
Man 0: 3 0 1 2 Woman 0: 3 0 2 1
Man 1: 1 2 0 Woman 1: 0 2 1 3
Man 2: 1 2 0 Woman 2: 0 1 2 3
Man 3: 2 0 3 1 Woman 3: 3 0
Notice that three things have changed: the list for man 1, the list for man 2 and the list for woman 3.
Suppose we next go to man 1. We engage him to woman 1. Man 3 appears after man 1 on woman 1’s list, so we have to delete that connection, obtaining:
Man 0: 3 0 1 2 Woman 0: 3 0 2 1
Man 1: 1 2 0 Woman 1: 0 2 1
Man 2: 1 2 0 Woman 2: 0 1 2 3
Man 3: 2 0 3 Woman 3: 3 0
Notice that two things have changed: the list for man 3 and the list for woman 1.
Suppose we next go to man 2. We engage him to woman 1, which requires breaking woman 1’s engagement to man 1 (making man 1 again available). Man 1 appears after man 2 on woman 1’s list, so we break that connection, obtaining:
Man 0: 3 0 1 2 Woman 0: 3 0 2 1
Man 1: 2 0 Woman 1: 0 2
Man 2: 1 2 0 Woman 2: 0 1 2 3
Man 3: 2 0 3 Woman 3: 3 0
Suppose we next go to man 3. We engage him to woman 2. Nobody appears on woman 2’s list after man 3, so we don’t have to remove any connections:
Man 0: 3 0 1 2 Woman 0: 3 0 2 1
Man 1: 2 0 Woman 1: 0 2
Man 2: 1 2 0 Woman 2: 0 1 2 3
Man 3: 2 0 3 Woman 3: 3 0
Now we go back to man 1 (because he’s still free). We engage him to woman 2, which requires breaking woman 2’s engagement to man 3 (making man 3 again available). Men 2 and 3 appear after man 1 on woman 2’s list, so we break those connections, obtaining:
Man 0: 3 0 1 2 Woman 0: 3 0 2 1
Man 1: 2 0 Woman 1: 0 2
Man 2: 1 0 Woman 2: 0 1
Man 3: 0 3 Woman 3: 3 0
Finally, the last free man is man 3. We engage him to woman 0. We could actually stop at this point, but according to the algorithm, we should notice that men 0, 2 and 1 all appear after man 3 on woman 0’s list, so we break those connections:
Man 0: 3 1 2 Woman 0: 3
Man 1: 2 Woman 1: 0 2
Man 2: 1 Woman 2: 0 1
Man 3: 0 3 Woman 3: 3 0
This, then, is our stable marriage solution.
An interesting property of this simple stable marriage algorithm is that it favors one group over the other. The approach above favors the men at the expense of the women. In fact, the final result will give each man his best possible match for stable marriage situations, and will give each woman her worst possible match. But there is no reason that the algorithm can’t be reversed with the women being favored over the men (just reversing the roles in the algorithm above).
You will also report in a column called “Choice” the relative position of the chosen partner in the original preference list and you will report the average of the choice column at the end of each sublist. For the following report, you will find the results favor the men:
Matches for men
Name Choice Partner
--------------------------------------
Man 0 1 Woman 3
Man 1 2 Woman 2
Man 2 1 Woman 1
Man 3 2 Woman 0
Mean choice = 1.5
Matches for women
Name Choice Partner
--------------------------------------
Woman 0 1 Man 3
Woman 1 2 Man 2
Woman 2 2 Man 1
Woman 3 2 Man 0
Mean choice = 1.75
For example, man 0 is paired with woman 3, and woman 3 was first on man 0’s original list. However, man 0 was the third on woman 3’s original list.
The stable marriage algorithm always converges on an answer, but it is possible that some people will end up without being paired (this is inevitable in the large sample input file where there are 40 men and 35 women). Remember that the original algorithm terminates when there are no men left who are free and have a nonempty preference list. People are unpaired in the final result if they run out of choices on their preference lists. Be careful not to report a “choice” value for these people and don’t include them in the calculation of the overall choice value.
You are going to write a Java program to implement the algorithm in which you will utilize List data structures. In order to represent a woman or a man, you will also need to define a class named Person.
Your Person class should at least have the following public methods:
- public void erasePartner()
- It makes this person engage with nobody (i.e., no partner).
- public boolean hasPartner()
- It returns true if this person currently engages with somebody.
- public int getPartner()
- It returns this person’s current partner. Notice that each woman and man has an implicit ID which is based on the position this person appears in the input file. All person’s IDs starts from 1 Men and women have separate ID numberings.
- public void setPartner(int partner)
- It sets this person’s current partner to be the one who has the passed-in ID.
- public String getName()
- It returns this person’s name shown in the input file.
- public boolean hasChoices()
- It returns true if this person’s preference list is currently non-empty.
- public int getFirstChoice()
- It returns the ID of the first person in this person’s preference list.
- public void addChoice(int person)
- It adds the specified person to this person’s preference list.
- public List getChoices()
- It returns this person’s preference list.
You are free to define other methods, public or private, which you deem necessary or helpful.
Besides, a Person object should at least have the following private fields:
- private String name
- It is this person’s name. Note that name can be same as or different from the person’s implicit ID.
- private int partner
- It is this person’s current partner. It can be none.
- private List preferences
- It is this person’s preference list. Note that it is an integer list whose elements are person IDs.
After class design, continue to write a Java program to implement the above described stable marriage algorithm. The program should also prompt users for the name of the input file. The output should be the display of two match tables, one for men and the other for women. At the end of each table, you have to report the mean choice for that group.
Code specifications:
- The header comment lines at the top of your java files contain a brief description of the program or the class. The description should be one or 2 lines long describing the purpose of the program or the class.
- You also have to include comment lines in all of your public methods, static or not.
- Use Javadoc’s comment formats for program and public methods documentation.
- Use descriptive variable names and method names.
- Define constants whenever appropriate.