Stable Match:Gale-Shapley algorithm（Implementation）

2290阅读　0评论2013-11-08　skyornig
分类：Java

                                     Stable Match:Gale-Shapley algorithm（Implementation） 

 Programing：
    Implement Gale-Shapley algorithm of the Stable Matching Problem in your favorite language, and give the matching result of attached ranking data (boys rankings.txt and girls rankings.txt), supposing that the ranking is sorted from high to low.
    这是一道经典的算法题，下面是该算法的伪代码：          

1: for m = 1 to M do

2:     partner[m] = NULL

3: end for

4: for w = 1 to W do

5:     partner[w] = NULL

6: end for

7: while TRUE do

8:     if there is no man m such that partner[m] = NULL then

9:         return;

10:     end if

11:     select such a man m arbitrarily;

12:     w= the first woman on m′s list to whom m have not yet proposed;

13:     if partner[w] == NULL then

14:        partner[w] = m; partner[m] = w;

15:     else if w prefers m to state[w] then

16:        partner[ partner[w] ] = NULL; partner[w] = m; partner[m] = w;

17:     else

18:     ; //do nothing means simply rejecting m;

19:     end if

20: end while

根据该伪代码，使用java做如下实现，对stable match问题感兴趣的同学可以试试，挺好玩的。

点击(此处)折叠或打开

  1. public class GaleShapleyAlgorithm {
  2.     public static final int numberOfPairs = 200;
  3.     public static String boysRank[][] = new String[numberOfPairs][numberOfPairs+1];//保存男生对女生的兴趣度排序
  4.     public static String girlsRank[][] = new String[numberOfPairs][numberOfPairs+1];//保存女生对男生的兴趣度排序
  5.     public static String partnerM[][] = new String[numberOfPairs][2];//保存男生对女生的匹配结果
  6.     public static String partnerW[][] = new String[numberOfPairs][2];//保存女生对男生的匹配结果
  7.     // 初始化boysRank二维数组和partnerM二维数组
  8.     public static void boysRank(String boysRank1[][]){
  9.         int numberOfMan = boysRank1[0].length-1;
  10.         for(int i=0; i<numberOfMan; i++){
  11.             for(int j=0; j<numberOfMan+1; j++){
  12.                 boysRank[i][j] = boysRank1[i][j];        
  13.             }
  14.         }
  15.         for(int i=0; i<partnerM.length; i++){
  16.             partnerM[i][0] = boysRank[i][0];
  17.             partnerM[i][1] = "null";            
  18.         }
  19.     }
  20.     // 初始化girlsRank二位数组和partnerW二维数组
  21.     public static void girlsRank(String girlsRank1[][]){
  22.         int numberOfW = girlsRank1[0].length-1;
  23.         for(int i=0; i<numberOfW; i++){
  24.             for(int j=0; j<numberOfW+1; j++){
  25.                 girlsRank[i][j] = girlsRank1[i][j];
  26.             }            
  27.         }
  28.         for(int i=0; i<partnerW.length; i++){
  29.             partnerW[i][0] = girlsRank[i][0];
  30.             partnerW[i][1] = "null";            
  31.         }
  32.     }
  33.     
  34.     //stable match:Gale-Shapley-Algorithm具体实现
  35.     public static void stableMatch(){        
  36.         while(true){
  37.             if(ifPartnerNull(partnerM)){
  38.                 break;
  39.             }
  40.             for(int i=0; i<partnerM.length; i++){
  41.                 // 尚未配对的男生
  42.                 if(partnerM[i][1].equals("null")){
  43.                     // 寻找配对伴侣
  44.                     for(int j=1; j<boysRank[0].length; j++){
  45.                         // 第j个女生是 该男生尚未求婚的第一个女生，向j求婚
  46.                         if(!boysRank[i][j].equals("null")){
  47.                             int index = searchArray(partnerW,boysRank[i][j]);
  48.                             // 女生j尚未配对
  49.                             if(partnerW[index][1].equals("null")){
  50.                                 partnerM[i][1] = boysRank[i][j];
  51.                                 partnerW[index][1] = partnerM[i][0];
  52.                                 boysRank[i][j] = "null"; // 求过婚 则设置null
  53.                                 break;
  54.                             }
  55.                     // 女生j已经配对，但是她更喜欢男生i
  56.                     else if(ifWPerferM(index,partnerW[index][1],partnerM[i][0])){
  57.                         int oldManindex = searchArray(partnerM,partnerW[index][1]);
  58.                         partnerM[i][1] = boysRank[i][j];
  59.                         partnerW[index][1] = partnerM[i][0];
  60.                         boysRank[i][j] = "null"; // 求过婚 则设置null 
  61.                         // 被踢掉的男生的 partner设置为null
  62.                         partnerM[oldManindex][1] = "null";
  63.                         break;
  64.                         }
  65.                             else{
  66.                                 boysRank[i][j] = "null";
  67.                                 break;
  68.                             }
  69.                         }
  70.                     }
  71.                 }
  72.             }
  73.         }        
  74.     }
  75.     // 判断女生是更喜欢当前求婚男生还是更喜欢已经配对的男生
  76.     public static boolean ifWPerferM(int womanIndex,String man, String perferMan){
  77.         int manIndex = -1;
  78.         int perferManIndex = -1;
  79.         for(int i=1; i<girlsRank[0].length; i++){
  80.             if(girlsRank[womanIndex][i].equals(man)){
  81.                 manIndex = i;
  82.             }
  83.             if(girlsRank[womanIndex][i].equals(perferMan)){
  84.                 perferManIndex = i;
  85.             }
  86.         }
  87.         if(perferManIndex < manIndex){
  88.             return true;
  89.         }else{
  90.             return false;
  91.         }        
  92.     }
  93.     // 查询特定值在二维数组中的位置
  94.     public static int searchArray(String array[][],String value){
  95.         int index= -1;
  96.         for(int i=0; i<array.length; i++){
  97.             if(array[i][0].equals(value)){
  98.                 return i;
  99.             }
  100.         }
  101.         return index;
  102.     }
  103.     // 是否有某位男生或者女生还没有配对
  104.     public static boolean ifPartnerNull(String partner[][]){
  105.         for(int i=0; i<partner.length; i++){
  106.             if(partner[i][1].equals("null")){
  107.                 return false;
  108.             }
  109.         }
  110.         return true;
  111.     }
  112.     public static void main(String[] args) throws IOException {
  113.         // TODO Auto-generated method stub
  114.         String girlsRankFilePath = "F:\\ Assignm1\\data-200pairs\\girls_rankings.txt";
  115.         String boysRankFilePath = "F:\\ Assignm1\\data-200pairs\\boys_rankings.txt";
  116.         String boysRank1[][] = TxtFileOp.readTxtFile(boysRankFilePath);
  117.         boysRank(boysRank1);
  118.         String girlsRank1[][] = TxtFileOp.readTxtFile(girlsRankFilePath);
  119.         girlsRank(girlsRank1);
  120.         stableMatch();
  121.         TxtFileOp.writeToTxt(partnerM, "partnerM.txt");// 将结果写入文件
  122.         TxtFileOp.writeToTxt(partnerW, "partnerW.txt");
  123.     }
  124. }
        上述java实现中有用到一些，读写txt的函数操作，这些并不是算法的核心，大家自己写一下即可。
        男生对女生的兴趣度排序数据：boys_rankings.txt。
        女生对男生的兴趣度排序数据：girls_rankings.txt。
        算法最终输出结果文件：partnerM.txt，partnerW.txt。


上一篇：安装AD 证书服务
下一篇：sakai 开发环境搭建（一）