0

Gale-Shapleyアルゴリズムを用いた安定結婚問題(安定マッチング)についての質問です。
このプログラムの人数を男女それぞれN人に拡張し、N組のカップルを作りたいのですが5人以上にする目処が立たなくて困っています。課題の期限が迫っていてたいへん焦っています。
以下のソースコードを書き換えてN組の安定マッチングが実現できるソースコードにしていただけ
環境はEclipseで、Java言語での記述です。
C言語のソースコード例は探せたのですが、力がなくJavaに書き換えることが上手くできませんでした。
すみません、よろしくお願い致します。

import java.util.Scanner;


/** Class GaleShapley **/
public class GaleShapley
{
  private int N, engagedCount;//プロポーズ回数
  private String[][] menPref;//男性の好み
  private String[][] womenPref;//女性の好み
  private String[] men;//男性
  private String[] women;//女性
  private String[] womenPartner;//女性のパートナー
  private boolean[] menEngaged;//男性の婚約者

  /** コンストラクタ **/
  public GaleShapley(String[] m, String[] w, String[][] mp, String[][] wp)
  {
    N = mp.length;//mp配列(menPref)の長さを取得
    engagedCount = 0;
    men = m;
    women = w;
    menPref = mp;
    womenPref = wp;
    menEngaged = new boolean[N];
    womenPartner = new String[N];
    calcMatches();
  }

  /** 全ての好みが一致するかの計算 **/
  private void calcMatches()
  {
  //プロポーズを男性の選好順序すべて終わるまで繰り返す
    while (engagedCount < N)
    {
      int free;
      //男性の選好順序すべて終わるまで繰り返す
      for (free = 0; free < N; free++)
      //もし、男性のプロポーズ回数が0でなければbreak
        if (!menEngaged[free])
          break;

      //男性の選好順序すべて終わり、かつ男性のプロポーズ回数がfree回でなければ繰り返す
      for (int i = 0; i < N && !menEngaged[free]; i++)
      {
        int index = womenIndexOf(menPref[free][i]);
        if (womenPartner[index] == null)
        {
          womenPartner[index] = men[free];
          menEngaged[free] = true;
          engagedCount++;
        }
        else
        {
          String currentPartner = womenPartner[index];
          if (morePreference(currentPartner, men[free], index))
          {
            womenPartner[index] = men[free];
            menEngaged[free] = true;
            menEngaged[menIndexOf(currentPartner)] = false;
          }
        }
      } 
    }
    printCouples();
  }

  /** 女性が現在のパートナーよりも新しいパートナーを好むかどうかをチェックする **/
  private boolean morePreference(String curPartner, String newPartner, int index)
  {
    for (int i = 0; i < N; i++)
    {
      //もし、新しい男性が女性の好みと一致したら:true
      if (womenPref[index][i].equals(newPartner))
        return true;
      //もし、現在の男性が女性の好みと一致したら:false
      if (womenPref[index][i].equals(curPartner))
        return false;
    }
    return false;
  }

  /** 男性の番号を取得 **/
  private int menIndexOf(String str)
  {
    for (int i = 0; i < N; i++)
    //もし、男性の名前がが与えられた文字列と一致したらiを返す
      if (men[i].equals(str))
        return i;
    //そうでなければ-1を返す
    return -1;
  }

  /** 女性の番号を取得 **/
  private int womenIndexOf(String str)
  {
    for (int i = 0; i < N; i++)
    //もし、女性の名前がが与えられた文字列と一致したらiを返す
      if (women[i].equals(str))
        return i;
    //そうでなければ-1を返す
    return -1;
  }

  /** 結果表示 **/
  public void printCouples()
  {
    System.out.println("カップルは以下の組で成立 ");
    for (int i = 0; i < N; i++)
    {
      System.out.println(womenPartner[i] +" "+ women[i]);
    }
  }

  /** main **/
  public static void main(String[] args) 
  {
    System.out.println("数値(n)を入力して下さい。");
    Scanner scan = new Scanner(System.in);

    int N = scan.nextInt();

    System.out.println("Gale Shapley Marriage Algorithm\n");
    /** 男性の要素 **/
    String[] m = {"M1", "M2", "M3", "M4", "M5"};
    /** 女性の要素 **/
    String[] w = {"W1", "W2", "W3", "W4", "W5"};

    /** 男性の選好順序 **/
    String[][] mp = {
      {"W5", "W2", "W3", "W4", "W1"}, 
      {"W2", "W5", "W1", "W3", "W4"}, 
      {"W4", "W3", "W2", "W1", "W5"}, 
      {"W1", "W2", "W3", "W4", "W5"},
      {"W5", "W2", "W3", "W4", "W1"}
    };

    /** 女性の選好順序 **/ 
    String[][] wp = {
      {"M5", "M3", "M4", "M1", "M2"}, 
      {"M1", "M2", "M3", "M5", "M4"}, 
      {"M4", "M5", "M3", "M2", "M1"},
      {"M5", "M2", "M1", "M4", "M3"}, 
      {"M2", "M1", "M4", "M3", "M5"}
    };

    GaleShapley gs = new GaleShapley(m, w, mp, wp); 
  }
}
2
  • 2
    このサイトではMarkdownという記法が使われているので、ソースコードをそのまま貼り付けると一部記号が文字装飾として扱われてしまいます。コード全体を範囲選択してからエディタ上部の {} ボタンを押すと、その範囲は記号やスペースもそのまま表示されるようになります。その前にソースコードを適切にインデントしておくと読みやすいですね。 / また知恵袋にも同じ質問を投稿されているようですが、一度「マルチポスト」という言葉を調べてみてください。 / 本題に移りますが、別にそのコードは5組でしか動作しないコードではなく、要素と選好順序を増やせば問題なく動くように思います。よって既に「N組の安定マッチングが実現できるソースコード」になっているわけですが、それでは不十分なのでしょうか?
    – unarist
    2017年2月4日 8:34
  • コメントどうもありがとうございます。 マルチポイントを検索しました。大変失礼でした。申し訳なく思います。以後繰り返しません。 記法の方も確認いたしました。次回から読みやすくするよう心がけます。 【本題】 ありがとうございます!仰られた通りです。要素と人数を正しく入力すれば問題ありませんでした。単純に自分が心配しすぎていたようでした。指摘されて初めて気づけました。どうもありがとうございました。大変勉強になりました。
    – shin44
    2017年2月4日 13:16

0

この質問に回答するには、ログインする必要があります。

のタグが付いた他の質問を参照する。