Description: The Gale–Shapley algorithm involves a number of rounds (or iterations ). In the first round, first a) each unengaged man proposes to the woman he prefers most, and then b) each woman replies maybe to her suitor she most prefers and no to all other suitors. She is then provisionally engaged to the suitor she most prefers so far, and that suitor is likewise provisionally engaged to her. In each subsequent round, first a) each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then b) each woman replies maybe to her suitor she most prefers (whether her existing provisional partner or someone else) and rejects the rest (again, perhaps including her current provisional partner). The provisional nature of engagements preserves the right of an already-engaged woman to trade up (and, in the process, to jilt her until-then partner).
To Search:
File list (Check if you may need any files):
GaleShapley.java
Download