GS 稳定匹配算法 Java实现

GS 稳定匹配算法 Java实现

算法描述

给定n个男人，n个女人，每个男人都有一张对所有女人的偏爱表，每个女人都有一张对所有的男人的偏爱表，要求设计一算法，产生一稳定匹配。

匹配过程

初始化所有的男人和女人都是自由的
while （存在男人m是自由的且还没对每个女人都求过婚）选择这样一个男人m令w是m的优先表中m还没求过婚的最高排名的女人if w是自由的(m,v)变成约会状态else w当前与m’约会if w更爱m’（对比m）m保持自由else w更爱m （对比m’）(m,v)变成约会状态m’变成自由endifendif

Java代码实现如下

GS类

import java.util.Arrays;public class GS {static int num = 4;static Woman women[] = new Woman[num];static Man men[] = new Man[num];public static void main(String[] args) {// 男女优先表int menArray[][] = { { 2, 3, 1, 0 }, { 2, 1, 3, 0 }, { 0, 2, 3, 1 }, { 1, 3, 2, 0 } };int womenArray[][] = { { 0, 3, 2, 1 }, { 0, 1, 2, 3 }, { 0, 2, 3, 1 }, { 1, 0, 3, 2 } };System.out.println("男生的优先表");for (int i = 0; i < num; i++) {Man m = new Man();int a[] = {0,0,0,0};for(int j=0; j<num; j++)a[j]=menArray[i][j];System.out.String(a));m.setRank(a);m.setId(i);men[i] = m;}System.out.println("女生的优先表");for (int i = 0; i < num; i++) {Woman w = new Woman();int a[] = {0,0,0,0};for(int j=0; j<num; j++)a[j]=womenArray[i][j];System.out.String(a));w.setRank(a);   w.setId(i);women [i]= w;}System.out.println("——————————————————");Man theMan = null;while ((theMan = findMan(men)) != null) {           pursue(theMan, women);for (int i = 0; i < num; i++) {System.out.println("男生" + i + "&" + "女生" + men[i].getPresent());}System.out.println("——————————————————");}System.out.println("GS finished");}static Man findMan(Man[] men) {for (int i = 0; i < men.length; i++) {if (!men[i].isDate()) {System.out.println("单身男生" + i);return men[i];}}System.out.println("没有单身男生");return null;}static void pursue(Man m, Woman[] women) {Woman w = women[m.Better()]];System.out.println("想追女生" + w.getId());if (!w.isDate()) {System.out.println("女生没有对象");date(m, w);System.out.println("在一起");} else {System.out.println("女生有对象");if (pk(m, w)) {System.out.println("换男友");date(m, w);} else {System.out.println("不换男友");m.Better() + 1);}}}static void date(Man m, Woman w) {if (!w.isDate()) {m.setDate(true);m.Id());w.setDate(true);w.Id());} else {m.setDate(true);m.Id());Present()].setDate(false);Present()].setPresent(100);w.Id());}}static boolean pk(Man m, Woman w) {System.out.println("优先表"&#Rank()));int former = 100;for (int i = 0; i < num; i++) {if (w.getRank()[i] == w.getPresent()) {former = i;break;}}int later = 100;for (int i = 0; i < num; i++) {if (w.getRank()[i] == m.getId()) {later = i;break;}}System.out.println("前任排行" + former + "  vs  挑战者排行" + later);if (later < former) {return true;} else {return false;}}
}

Man类

public class Man {private int id;private int better = 0; // 追求过几位女生int[] rank = {0,0,0,0};private boolean date = false;private int present = 100;public int getId() {return id;}public void setId(int id) {this.id = id;}public int getBetter() {return better;}public void setBetter(int better) {this.better = better;}public int[] getRank() {return rank;}public void setRank(int[] rank) {this.rank = rank;}public boolean isDate() {return date;}public void setDate(boolean date) {this.date = date;}public int getPresent() {return present;}public void setPresent(int present) {this.present = present;}}

Woman类

public class Woman {private int id;int[] rank = {0,0,0,0};private boolean date = false;private int present = 100;public int getId() {return id;}public void setId(int id) {this.id = id;}public int[] getRank() {return rank;}public void setRank(int[] rank) {this.rank = rank;}public boolean isDate() {return date;}public void setDate(boolean date) {this.date = date;}public int getPresent() {return present;}public void setPresent(int present) {this.present = present;}
}

运行结果如下

男生的优先表
[2, 3, 1, 0]
[2, 1, 3, 0]
[0, 2, 3, 1]
[1, 3, 2, 0]
女生的优先表
[0, 3, 2, 1]
[0, 1, 2, 3]
[0, 2, 3, 1]
[1, 0, 3, 2]
——————————————————
单身男生0
想追女生2
女生没有对象
在一起
男生0&女生2
男生1&女生100
男生2&女生100
男生3&女生100
——————————————————
单身男生1
想追女生2
女生有对象
优先表[0, 2, 3, 1]
前任排行0  vs  挑战者排行3
不换男友
男生0&女生2
男生1&女生100
男生2&女生100
男生3&女生100
——————————————————
单身男生1
想追女生1
女生没有对象
在一起
男生0&女生2
男生1&女生1
男生2&女生100
男生3&女生100
——————————————————
单身男生2
想追女生0
女生没有对象
在一起
男生0&女生2
男生1&女生1
男生2&女生0
男生3&女生100
——————————————————
单身男生3
想追女生1
女生有对象
优先表[0, 1, 2, 3]
前任排行1  vs  挑战者排行3
不换男友
男生0&女生2
男生1&女生1
男生2&女生0
男生3&女生100
——————————————————
单身男生3
想追女生3
女生没有对象
在一起
男生0&女生2
男生1&女生1
男生2&女生0
男生3&女生3
——————————————————
没有单身男生
GS finished

更多细节请参考：