3

項目 (名前) の 1 つのリストからペアを選択する必要があるコードのセグメントを含むプログラムを作成しています。

ArrayList<String>最初のリストは、人々の一意の名前をすべて含む単一のリストから取得されます。

私の試みは次のとおりです。

//Performance is not really a focus as the lists are small (20 ~ 60 elements),
//thus I use a SecureRandom instead of a Random.
SecureRandom rnd = new SecureRandom();

//List of names
ArrayList<String> Names = new ArrayList<>();

//Names populated somewhere here..

//Make a secondary array which houses the available names...
ArrayList<String> AvailNames = new ArrayList<>();
AvailNames.addAll(Names);

LinkedHashMap<String, String> NamePair = new LinkedHashMap<>();
Iterator<String> Iter = Names.iterator();

// LOOP A
while(Iter.hasNext()){
    String name = Iter.next();
    int index;

   /*
    * LOOP B
    * Find a unique pair randomly, looping if the index is the same.
    * Not the most efficient way, but gets the job done...
    */
    while(true){
        index = rnd.nextInt(AvailNames.size());
        if(!AvailNames.get(index).equals(name)){
            break;
        }
    }

    NamePair.put(name, AvailNames.remove(index));
}

名前の数が奇数の場合、LOOP B(上記を参照) が無期限に実行されるという問題に遭遇します。

問題は、すべてのペアが取得されたときに、残っている最後の名前のペアが一意ではないことがあり、if ステートメントが真にならないことがあるという事実にあることがわかりました。

たとえば、次のリストを見てください。

  1. あ
  2. B
  3. ハ
  4. D
  5. え

プログラムは、実行中に A から D をソートして、次のような名前のペアを作成します。

  1. A - B
  2. B - C
  3. CD
  4. D - C

これはE - E、ペアとして許可されていない最終的なペアとして残ります (アイテム/名前が一意ではないため)。ペアの割り当てはランダムなので、うまくいくこともあればうまくいかないこともあり、率直に言って非常に面倒です...

解決策は非常に簡単だと確信していますが、何らかの理由でこの問題を回避する方法が見つからないようです。どんな助けでも大歓迎です。

4

3 に答える 3

3

この状況に陥ったことを検出し、最後AvailNameに、ランダムに選択された前のペアの 2 番目の要素と交換することができます。たとえば、2 番目のペアを選択した場合、それを BE に変更し、最後のペアは EC になります。

これは常に、それぞれが異なる 1 番目と 2 番目の要素を持つ 2 つのペアを生成します。選択されたペアは、最初の要素として E を持つことはできません (これを行う唯一のペアを生成しようとしています)、またはその 2 番目の要素として E を持つことはできません (そうでなければ E はありません)。であるAvailName）。

于 2013-11-09T12:04:32.693 に答える
2

ちょっとした考え; 可能なすべての一意のペアを計算し、そこからランダムにサンプリングできます。

これは O(n 2 ) であるため、多数の名前では遅くなる可能性があることに注意してください。Listまた、 n(n 2 -1)/2 個の要素が含まれているため、newはかなり大きくなります。

次に例を示します。

public static void main(String args[]) {
    final List<String> in = new ArrayList<String>() {
        {
            add("A");
            add("B");
            add("C");
            add("D");
            add("E");
        }
    };
    final List<String[]> pairs = new ArrayList<>();
    for (int i = 0; i < in.size(); ++i) {
        for (int j = i + 1; j < in.size(); ++j) {
            pairs.add(new String[]{in.get(i), in.get(j)});
        }
    }
    Collections.shuffle(pairs);
    for (final String[] pair : pairs) {
        System.out.println(Arrays.toString(pair));
    }
}

出力：

[B, E]
[A, C]
[A, E]
[A, B]
[B, D]
[C, D]
[C, E]
[B, C]
[A, D]
[D, E]

newList<String[]> pairsを作成してから、 input をループしますList。各反復では、入力の残りをループします。これにより、同じペアが再び逆になることはありません。

設定したら、それpairsを単純shuffleにして、必要な数のペアを取ります. 一様分布からのサンプルを考えるとRandom、 の順序付けの確率が等しくなるはずですpairs。SecureRandomを他のshuffleメソッドに渡すこともできます。

于 2013-11-09T12:05:42.323 に答える