STABLE MARRIAGE PROBLEM USING STACKS IN JAVA

Definition

Assume you have two sets of people. The sets have the same size (n) and do not overlap.

Find a set of n pairs such that a is from the first set, b is from the second set, and that all pairs satisfy some constraints.

For the stable marriage rule each person ranks the people in the other set. n couples are chosen. If there exists a man and a woman who are not married to each other but who would both prefer each other to their actual partners the assignment is said to be unstable.

If no such pair exists the assignment is said to be stable.

Project 1

In project 1 you will use backtracking to solve a stable marriage problem. We are not considering marriage preferences but pairs programming preferences. The input to the program will be given as: # of pairs to form (n) senior programmer 0 name preferences for junior programmer (integers 0..n-1) senior programmer 1 name preferences for junior programmer (integers 0..n-1)

senior programmer n-1 name preferences for junior programmer (integers 0..n-1) junior programmer 0 name preferences for senior programmer (integers 0..n-1) junior programmer n-1 name preferences for senior programmer (integers 0..n-1)

REQUIREMENTS

Must use backtracking and a stack to solve the problem.

The Resulting Match (if any) must be printed out. I would prefer the format to be: Team 0: senior programmer name, junior programmer name Team 1: senior programmer name, junior programmer name etc.

The main program to run your code should be in a class named Project1

Approach

Can you set up a method to determine if n pairs are stable or not?

This is a obvious need for the algorithm. What input information does it need?

What information needs to be saved on the stack?

How are you going to input the information for the problem into your program?

How are you going to test portions of your program?

Input and Guidelines

Input to this problem will come from a file. The file contains the number of pairings to make and two arrays indicating the preferences of each side. The input data will come from a file Project1TestData.txt and will be formatted as follows:

4 // number of pairings to make

Bobbie // First persons name in group A

0 1 2 3 // Bobs preferences (0 highest)

Ted // Second persons name in group A

2 0 1 3

Gina

3 2 1 0

Harry

0 2 1 3

Mel // First pers ons name in group B

3 2 1 0 // Mels preferences (0 highest)

Barb

2 1 3 0

Olive

2 3 1 0

Sam

2 0 1 3

Your program is to determine a pairing where there exist no two programmers that are not paired but would prefer each other to their actual partners. Your output upon finding a suitable pairing should be a list of the team pairs.

Team 0: Gina and Mel

Team 1: Harry and Sam

Team 2: Bobbie and Olive

Team 3: Ted and Barb

If no such pairing exists you should output the message: No stable pairing exists.

Program Guidelines

Your main program should be in a class named Project1.

Your name should be in the comments at the top of each source file.

Your variable names should be meaningful, they should reflect the usage or contents of the variable.

You should have Javadoc block comments for each class and non-trivial method.