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 mens 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 Joes 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 otherfor (each successor q of m on w's list) {delete w from q's preference listdelete q from w's preference list}}

Consider, for example, the following short input:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1Man 1: 1 2 0 3 Woman 1: 0 2 1 3Man 2: 1 3 2 0 Woman 2: 0 1 2 3Man 3: 2 0 3 1 Woman 3: 3 0 2 1

It doesnt 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 3s list. Thus, we delete those connections.

Man 0: 3 0 1 2 Woman 0: 3 0 2 1Man 1: 1 2 0   Woman 1: 0 2 1 3Man 2: 1 2 0   Woman 2: 0 1 2 3Man 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 1s list, so we have to delete that connection, obtaining:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1Man 1: 1 2 0   Woman 1: 0 2 1Man 2: 1 2 0   Woman 2: 0 1 2 3Man 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 1s engagement to man 1 (making man 1 again available). Man 1 appears after man 2 on woman 1s list, so we break that connection, obtaining:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1Man 1: 2 0     Woman 1: 0 2Man 2: 1 2 0   Woman 2: 0 1 2 3Man 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 2s list after man 3, so we dont have to remove any connections:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1Man 1: 2 0     Woman 1: 0 2Man 2: 1 2 0   Woman 2: 0 1 2 3Man 3: 2 0 3   Woman 3: 3 0

Now we go back to man 1 (because hes still free). We engage him to woman 2, which requires breaking woman 2s engagement to man 3 (making man 3 again available). Men 2 and 3 appear after man 1 on woman 2s list, so we break those connections, obtaining:

Man 0: 3 0 1 2 Woman 0: 3 0 2 1Man 1: 2 0     Woman 1: 0 2Man 2: 1 0     Woman 2: 0 1Man 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 0s list, so we break those connections:

Man 0: 3 1 2   Woman 0: 3Man 1: 2       Woman 1: 0 2Man 2: 1       Woman 2: 0 1Man 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 cant 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 menName           Choice  Partner--------------------------------------Man 0             1    Woman 3Man 1             2    Woman 2Man 2             1    Woman 1Man 3             2    Woman 0Mean choice = 1.5Matches for womenName           Choice  Partner--------------------------------------Woman 0           1    Man 3Woman 1           2    Man 2Woman 2           2    Man 1Woman 3           2    Man 0Mean choice = 1.75

For example, man 0 is paired with woman 3, and woman 3 was first on man 0s original list. However, man 0 was the third on woman 3s 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 dont 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 persons 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 persons IDs starts from 1 Men and women have separate ID numberings.
• public void setPartner(int partner)
  • It sets this persons current partner to be the one who has the passed-in ID.
• public String getName()
  • It returns this persons name shown in the input file.
• public boolean hasChoices()
  • It returns true if this persons preference list is currently non-empty.
• public int getFirstChoice()
  • It returns the ID of the first person in this persons preference list.
• public void addChoice(int person)
  • It adds the specified person to this persons preference list.
• public List getChoices()
  • It returns this persons 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 persons name. Note that name can be same as or different from the persons implicit ID.
• private int partner
  • It is this persons current partner. It can be none.
• private List preferences
  • It is this persons 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 Javadocs comment formats for program and public methods documentation.
• Use descriptive variable names and method names.
• Define constants whenever appropriate.