Write a program that solves the classic “stable marriage” problem. 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 is #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, see the following input line in 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 choice for marriage is woman #10, his second choice is woman #8, and so on. Any women not listed are considered unacceptable to Joe.

The stable marriage problem is solved by the following algorithm:

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

Transcribed Image Text:

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.