Stable Marriage Problem

Stable Marriage Problem (SMP)
穩定婚姻配對

這個問題主要是處理男性與女性間的婚姻配對
運用每個男性心目中對每個女性的排名
以及每個女性心目中對每個男性的排名

使每一對夫婦對彼此伴侶的排名不會產生
(M,W)與(m,w)中
M男對w女的排名高於現任妻子W
且w女對M男的排名高於現任丈夫m男

我參考這個網頁

Math Site: Stable Marriage Problem

玩一玩配對遊戲 推測出來的配對方法

配對方法：

    尋找男性排名最高的女性

        女性是否單身

            是，配對

            否，找尋女性現在的配對男性 在女性心目中排名 比較

                排名較大 取代 並為被取代的重新尋找配對

                排名較小 找下一位

                (女性優先則男女互換)


＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝


配對部分的程式碼(Java)


   public void match(int mw){
      int i;
      for( i=1 ; i <= n ; i++ ){      //清空單身狀態
         single[i]=true;
      }
      if(mw == 1){
         for( i = 1; i <= n ; i++){
            stableByMan(i);
         }
      }
      else{
         for( i = 1; i <= n ; i++){
            stableByWoman(i);
         }
      }
   }

private void stableByMan(int man){
      int pm,pw,i;
      boolean s;
      s = false;
      i=1;
      while(!s){
         pw = wmrA.getWmr(man,i);       //wmr 為 在男性心目中 對女性的排名
         if (single[pw]==true){   //單身 直接配對
            x[man] = pw;
            y[pw] = man;
            single[pw] = false;
            s = true;         //配對成功
         }
         else{               //有伴 先比較
            pm = y[pw];         //讀取已配好的伴
            if(mwrA.getRwm(pw,man) < mwrA.getRwm(pw,pm)){   //現在的與之前的相比
               x[man] = pw;
               y[pw] = man;
               s=true;         //配對成功
               stableByMan(pm);   //pm重新配對
            }
            else{
               i++;         //找下一位
            }
         }
      }
   }