Background: The Gale-Shapley Algorithm is useful for providing a single stable matching. The key word is...

  

Transcribed Image Text:

Background: The Gale-Shapley Algorithm is useful for providing a single stable matching. The key word is single. One of the drawbacks with this algorithm despite its O(n) running-time is that it does not return every possible stable matching. Objective: Create a program that is able to take an instance of the Stable Matching Problem and return the total number possible stable matches. Input Format: You must create an input file called "input1.txt". You will then read from the file to obtain the following: How many men/women will there be? Each preference list for the men. Each preference list for the women. You will separate numbers in each list with a space (see examples below) For more understanding see the example #1 below. The 4 at the top of the file tells me there are 4 men and 4 women There are 8 total lines representing the preference lists The first 4 lines are the preference list for the men The last 4 lines are the preference list for the women EXAMPLE #1: Given an inputl.txt file of 4 1234 2134 3412 4312 2134 1234 4312 3412 Your output should be: 4 EXAMPLE #2: Given an inputl.txt file of 2 12 12 12 12 Your output should be: 1 Important Note: This project will be computationally intensive since it will have a worst case running time of O(n!). You can use the examples to check your program. I expect your program to be able to handle 10 men and women. If your program fails to hit this mark you will lose points. Background: The Gale-Shapley Algorithm is useful for providing a single stable matching. The key word is single. One of the drawbacks with this algorithm despite its O(n) running-time is that it does not return every possible stable matching. Objective: Create a program that is able to take an instance of the Stable Matching Problem and return the total number possible stable matches. Input Format: You must create an input file called "input1.txt". You will then read from the file to obtain the following: How many men/women will there be? Each preference list for the men. Each preference list for the women. You will separate numbers in each list with a space (see examples below) For more understanding see the example #1 below. The 4 at the top of the file tells me there are 4 men and 4 women There are 8 total lines representing the preference lists The first 4 lines are the preference list for the men The last 4 lines are the preference list for the women EXAMPLE #1: Given an inputl.txt file of 4 1234 2134 3412 4312 2134 1234 4312 3412 Your output should be: 4 EXAMPLE #2: Given an inputl.txt file of 2 12 12 12 12 Your output should be: 1 Important Note: This project will be computationally intensive since it will have a worst case running time of O(n!). You can use the examples to check your program. I expect your program to be able to handle 10 men and women. If your program fails to hit this mark you will lose points.

Answer rating: 100% (QA)

Background The GaleShapley Algorithm is useful for providing ... View the full answer