IN JAVA

Map, HashMap, and ArrayList data strutures are not allowed.

The assignment is to write a console-based program to solve the Stable Matching Problem using the Gale-Shapley algorithm. You must use a linked list for the preference list of each man and woman. See the posting Stable Matching.ppt in the Algorithms folder. There are also numerous references to the Gale-Shapley algorithm on the Internet.

The input to the program will be a text file listing, in order,

1. the number n of men and women,

2. the names of the n men,

3. the names of the n women,

4. the list of preferences for each of the n men, and

5. the list of preferences for each of the n women.

For example, consider the following example of the contents of a file

----------------------------------------------------

5

Brian George John Robert Stephen

Anne Joyce Nancy Patricia Susan

// Preferences Men:

John: Susan Joyce Nancy Patricia Anne

Robert: Nancy Anne Joyce Susan Patricia

Brian: Patricia Susan Joyce Anne Nancy

Stephen: Joyce Anne Susan Nancy Patricia

George: Nancy Joyce Patricia Susan Anne

// Preferences Women:

Nancy: John Brian Stephen Robert George

Joyce: George John Stephen Robert Brian

Patricia: George Brian Robert Stephen John

Anne: George Stephen John Brian Robert

Susan: Brian George Stephen John Robert

----------------------------------------------------

The output will be the list of arranged marriages.

----------------------------------------------------

Marriages:

(Anne,Stephen)

(Joyce,George)

(Susan,John)

(Patricia,Brian)

(Nancy,Robert)

----------------------------------------------------

The program will operate as follows:

1. Ask the user for the name of the input file

2. Display the number of men and women, and the lists of men and women

3. Display the list of mens preferences and the list of womens preferences

4. Ask the user to select one of the following:

Men Propose

Women Propose

5. Ask the user for the go-ahead to apply the Gale-Shapley algorithm

6. Display the list of marriages.

The submission should include a printout of using the data given above.