2 Replies - 237 Views - Last Post: 25 April 2019 - 09:56 PM Rate Topic: -----

#1 mikel1   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 25-April 19

Stable Marriage Problem

Posted 25 April 2019 - 08:10 PM

I am working on a homework assignment that is the stable marriage problem using the Gale-Shapley algorithm and I can't figure out what is wrong. In the output, it isn't pairing anybody with another partner... no error message though. Most of the code is given for this assignment, I have only put in my portion of this code.

[
   public static void makeMatches(List<Person> list1, List<Person> list2) {
    	// set each person to be free
    	for (Person m : list1) {
    		m.erasePartner();
    	}
    	
    	for (Person w: list2) {
    		w.erasePartner();
    	}
    	
    	
    	for (Person m : list1) {
    		for (Person w : list2) {
    			// find man with nonempty preference list that is free    	
    			while (m.hasChoices() && !m.hasPartner()) {
    				// first woman on man's list
    				int w1 = m.getFirstChoice();
    				
    				for (Person m1 : list1) {
    					// if chosen woman is free, set her to be man's partner
    					if (!w.hasPartner()) {m.setPartner(w1);

    					// if chosen woman has partner, set her to be free and engage her and man
    					} else if (w.hasPartner()) {
    						if (w.getPartnerRank() < w.getChoices().indexOf(m)) {
    						w.erasePartner();
    						m.setPartner(w1);
    						}
    					}
    				}
    			}
    		}
    	}
    }]
:code:

output:
Matches for men
Name Choice Partner
--------------------------------------
Man 0 1 Woman 3
Man 1 1 Woman 1
Man 2 1 Woman 1
Man 3 1 Woman 2
Mean choice = 1.0

Matches for women
Name Choice Partner
--------------------------------------
Woman 0 -- nobody
Woman 1 -- nobody
Woman 2 -- nobody
Woman 3 -- nobody
Mean choice = NaN

This post has been edited by modi123_1: 25 April 2019 - 08:34 PM
Reason for edit:: In the future please use the [code] tag button in the editor


Is This A Good Question/Topic? 0
  • +

Replies To: Stable Marriage Problem

#2 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 14995
  • View blog
  • Posts: 59,872
  • Joined: 12-June 08

Re: Stable Marriage Problem

Posted 25 April 2019 - 08:35 PM

Are you certain your 'else if' should not just be an 'else'?
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12585
  • View blog
  • Posts: 45,715
  • Joined: 27-December 08

Re: Stable Marriage Problem

Posted 25 April 2019 - 09:56 PM

Your logic here is not correct. Get the man m. Then go through m's preference list. You should *not* be iterating through all the women here.
for (Person m : list1) {
    for (Person w : list2) {



Note as well that a man should only propose to a woman he has not previously propositioned. If the woman says no or dumps him, then the man should take the hint and not persist.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1