Java Collections Framework - Building Java Programs: A Back to Basics Approach - page 714

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:
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
3. Write a program that solves the classic “random writer” problem. This problem deals with reading input files of text
and examining the frequencies of characters. On the basis of those frequencies, you can generate randomized output
that appears to match the writing style of the original document. The longer the chains you link together, the more
accurate the random text will sound. For example, level 4 random text (text with chains of 4 letters long) generated
from Tom Sawyer might look like this: “en themself, Mr. Welshman, but him awoke, the balmy shore. I'll give him
that he couple overy because in the slated snufflindeed structure's kind was rath. She said that the wound the door a
fever eyes that WITH him.” Level 10 random text from the same source might look like this: “you understanding that
they don't come around in the cave should get the word beauteous was over-fondled, and that together and decided
that he might as we used to do—it's nobby fun. I'll learn you.” Search the internet for “Random Writer” to learn
more about this problem, such as the specification posed by computer scientist Joseph Zachary.