Feb 17, 2019 All 13 C 4 Java 2 E 1 JavaScript 1 Jupyter Notebook 1 Python 1 R 1 Smalltalk 1 TeX 1. Solving the Stable Marriage/Matching Problem with the Gale–Shapley algorithm. This is a Stable matching program that will take N men and N women and match them using the Gale–Shapley algorithm. This program runs in O(n^2) time.
Gale-Shapley stable matching algorithm implemented in Java. ConnorD/Gale-Shapley. Gale-Shapley stable matching algorithm implemented in Java. Input: a text file that defines the preference list of each man and woman, where there are n number of men and n number of women.
The Stable Marriage Problem states that given N men and N women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable” (Source Wiki).
Consider the following example.
Let there be two men m1 and m2 and two women w1 and w2.
Let m1‘s list of preferences be {w1, w2}
Let m2‘s list of preferences be {w1, w2}
Let w1‘s list of preferences be {m1, m2}
Let w2‘s list of preferences be {m1, m2}
The matching { {m1, w2}, {w1, m2} } is not stable because m1 and w1 would prefer each other over their assigned partners. The matching {m1, w1} and {m2, w2} is stable because there are no two people of opposite sex that would prefer each other over their assigned partners.
It is always possible to form stable marriages from lists of preferences (See references for proof). Following is Gale–Shapley algorithm to find a stable matching:
The idea is to iterate through all free men while there is any free man available. Every free man goes to all women in his preference list according to the order. For every woman he goes to, he checks if the woman is free, if yes, they both become engaged. If the woman is not free, then the woman chooses either says no to him or dumps her current engagement according to her preference list. So an engagement done once can be broken if a woman gets better option. Time Complexity of Gale-Shapley Algorithm is O(n2).
Following is complete algorithm from Wiki
Input & Output: Input is a 2D matrix of size (2*N)*N where N is number of women or men. Rows from 0 to N-1 represent preference lists of men and rows from N to 2*N – 1 represent preference lists of women. So men are numbered from 0 to N-1 and women are numbered from N to 2*N – 1. The output is list of married pairs.
Following is the implementation of the above algorithm.
C++
#include <iostream>#include <stdio.h>#define N 4 // This function returns true if woman 'w' prefers man 'm1' over man 'm' boolwPrefersM1OverM(intprefer[2*N][N], intw, intm, intm1) // Check if w prefers m over her current engagment m1 { // If m1 comes before m in lisr of w, then w prefers her if(prefer[w][i] m1) // If m cmes before m1 in w's list, then free her current if(prefer[w][i] m) } // Prints stable matching for N boys and N girls. Boys are numbered as 0 to voidstableMarriage(intprefer[2*N][N]) // Stores partner of women. This is our output array that // stores paing information. The value of wPartner[i] // indicates the partner assigned to woman N+i. Note that // the woman numbers between N and 2*N-1. The value -1 intwPartner[N]; // An array to store availability of men. If mFree[i] is // false, then man 'i' is free, otherwise engaged. memset(wPartner, -1, sizeof(wPartner)); intfreeCount = N; // While there are free men { intm; if(mFree[m] false) // One by one go to all women according to m's preferences. for(inti = 0; i < N && mFree[m] false; i++) intw = prefer[m][i]; // The woman of preference is free, w and m become // partners (Note that the partnership maybe changed // later). So we can say they are engaged not married { mFree[m] = true; } else// If w is not free // Find current engagement of w // If w prefers m over her current engagement m1, // then break the engagement between w and m1 and if(wPrefersM1OverM(prefer, w, m, m1) false) wPartner[w-N] = m; mFree[m1] = false; } // End of Else } // End of the for loop that goes to all women in m's list // Print the solution for(inti = 0; i < N; i++) } // Driver program to test above functions { {5, 4, 6, 7}, {4, 5, 6, 7}, {0, 1, 2, 3}, {0, 1, 2, 3}, stableMarriage(prefer); return0; |
Java
importjava.util.*; classGFG staticintN = 4; // This function returns true if woman staticbooleanwPrefersM1OverM(intprefer[][], intw, { // her current engagment m1 { // then w prefers her current engagement, if(prefer[w][i] m1) // then free her current engagement if(prefer[w][i] m) } } // Prints stable matching for N boys and // N-1. Girls are numbereed as N to 2N-1. { // output array that stores paing information. // The value of wPartner[i] indicates the partner // numbers between N and 2*N-1. The value -1 intwPartner[] = newint[N]; // An array to store availability of men. // free, otherwise engaged. Arrays.fill(wPartner, -1); while(freeCount >0) // Pick the first free man intm; if(mFree[m] false) // according to m's preferences. for(inti = 0; i < N && { // w and m become partners (Note that // So we can say they are engaged not married { mFree[m] = true; } else// If w is not free // Find current engagement of w // If w prefers m over her current engagement m1, // then break the engagement between w and m1 and if(wPrefersM1OverM(prefer, w, m, m1) false) wPartner[w - N] = m; mFree[m1] = false; } // End of Else // to all women in m's list // Print the solution for(inti = 0; i < N; i++) System.out.print(' '); wPartner[i]); } // Driver Code { {5, 4, 6, 7}, {4, 5, 6, 7}, {0, 1, 2, 3}, {0, 1, 2, 3}}; } |
Output:
References:
http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture5.pdf
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Recommended Posts:
Permalink
Join GitHub today
Gale Shapley Matching
GitHub is home to over 40 million developers working together to host and review code, manage projects, and build software together.
Sign up
Gale Shapley Java Program Pdf
1 contributor
| importjava.util.*; |
| importjava.io.*; |
| importjava.io.IOException; |
| publicclassStableMatching { |
| // just associate each man or woman ranker with an index |
| List<String> men =null; |
| List<String> women =null; |
| Map<String, List<String>> menRanking =null; |
| Map<String, List<String>> womenRanking =null; |
| publicstaticvoidmain(String[] args) { |
| // first, we need to parse the input data into appropriate data structures |
| newStableMatching(args[0]); |
| } |
| publicStableMatching(StringfilePath) { |
| BufferedReader fileReader =null; |
| // initialize our data structures |
| men =newArrayList<String>(); |
| women =newArrayList<String>(); |
| menRanking =newHashMap<String, List<String>>(); |
| womenRanking =newHashMap<String, List<String>>(); |
| // we will parse the input data in this method, work on matching in the doMatching() method |
| // also make sure we're safe from file I/O error |
| try { |
| String currentLineString =null; |
| String[] currentLineArray =null; |
| // input file reader |
| fileReader =newBufferedReader(newFileReader(filePath)); |
| // parse data and store in data structures we can work with later |
| while ((currentLineString = fileReader.readLine()) !=null) { |
| // now split the line into array using spaces as delimeter |
| currentLineArray = currentLineString.split(''); |
| int numberOfPeople = currentLineArray.length -1; |
| String ranker = currentLineArray[0]; |
| // preference list for the current ranker |
| List<String> prefList =Arrays.asList(Arrays.copyOfRange(currentLineArray, 1, currentLineArray.length)); |
| // add the women if they haven't already |
| if (women.size() 0) { |
| // women is a subset of the line array |
| women.addAll(prefList); |
| } |
| boolean isWoman =false; |
| for(String currentWoman : women) { |
| if (ranker.equals(currentWoman)) { |
| isWoman =true; |
| } |
| } |
| // is this a man currently ranking?? |
| if (isWoman false) { |
| // add male individual to our list |
| men.add(ranker); |
| // store their ranking |
| menRanking.put(ranker, prefList); |
| } else { |
| // now store this woman's ranking |
| womenRanking.put(ranker, prefList); |
| } |
| } |
| } catch (IOException e) { |
| e.printStackTrace(); |
| } finally { |
| try { |
| if (fileReader !=null) { |
| // close reader, good practice |
| fileReader.close(); |
| // assuming no file I/O errors, and we're done storing data, let's now match couples |
| // this is the bulk of the algorithm |
| Map<String, String> matches = doMatching(); |
| // output results |
| for(Map.Entry<String, String> matching:matches.entrySet()){ |
| System.out.println(matching.getKey() +''+ matching.getValue()); |
| } |
| // ensure stability |
| // if(checkMatches(matches)){ |
| // System.out.println('Stable matching'); |
| // } else { |
| // System.out.println('Unstable matching'); |
| // } |
| } |
| } catch (IOException ex) { |
| ex.printStackTrace(); |
| } |
| } |
| } |
| privateMap<String, String>doMatching() { |
| // where we map woman to man |
| Map<String, String> matches =newTreeMap<String, String>(); |
| // free men starts off as all men |
| List<String> freeMen =newLinkedList<String>(); |
| freeMen.addAll(men); |
| // loop until no more free men |
| while(!freeMen.isEmpty()) { |
| String currentMan = freeMen.remove(0); |
| List<String> currentManPrefers = menRanking.get(currentMan); |
| for(String woman : currentManPrefers) { |
| if(matches.get(woman) null) { // this woman is not matched |
| // match these two |
| matches.put(woman, currentMan); |
| break; |
| } else { |
| String otherMan = matches.get(woman); |
| List<String> currentWomanRanking = womenRanking.get(woman); |
| if(currentWomanRanking.indexOf(currentMan) < currentWomanRanking.indexOf(otherMan)){ |
| //this woman prefers this man to the man she's engaged to |
| matches.put(woman, currentMan); |
| freeMen.add(otherMan); |
| break; |
| } |
| } |
| } |
| } |
| // return the matching |
| return matches; |
| } |
| // private boolean checkMatches(Map<String, String> matches) { |
| // if(!matches.keySet().containsAll(women)) { |
| // return false; |
| // } |
| // |
| // if(!matches.values().containsAll(men)) { |
| // return false; |
| // } |
| // |
| // Map<String, String> invertedMatches = new TreeMap<String, String>(); |
| // |
| // for(Map.Entry<String, String> couple:matches.entrySet()) { |
| // invertedMatches.put(couple.getValue(), couple.getKey()); |
| // } |
| // |
| // for(Map.Entry<String, String> couple:matches.entrySet()) { |
| // // women |
| // List<String> shePrefers = womenRanking.get(couple.getKey()); |
| // List<String> herPrefList = new LinkedList<String>(); |
| // shePrefers.addAll(shePrefers.subList(0, shePrefers.indexOf(couple.getValue()))); |
| // |
| // // men |
| // List<String> hePrefers = menRanking.get(couple.getValue()); |
| // List<String> hisPrefList = new LinkedList<String>(); |
| // hePrefers.addAll(hePrefers.subList(0, hePrefers.indexOf(couple.getValue()))); |
| // |
| // for(String man : herPrefList) { |
| // String menFinace = invertedMatches.get(man); |
| // List<String> thisManPrefers = menRanking.get(man); |
| // |
| // if(thisManPrefers.indexOf(menFinace) > thisManPrefers.indexOf(couple.getKey())){ |
| // return false; |
| // } |
| // } |
| // |
| // for(String woman : hisPrefList){ |
| // String womenFinace = matches.get(woman); |
| // List<String> thisWomanPrefers = womenRanking.get(woman); |
| // |
| // if(thisWomanPrefers.indexOf(womenFinace) > thisWomanPrefers.indexOf(couple.getValue())) { |
| // return false; |
| // } |
| // } |
| // |
| // } |
| // |
| // return true; |
| // } |
| } |
Java Program Hello World
Copy lines Copy permalink