3

基本的に、私は25人の異なる人を含む配列を持っています。同じ人の複製を使用せずに、これらの人から5人を選択し、すべての組み合わせを可能にする必要があります。

私がそれを行うことを考えることができる唯一の論理的な方法は、5つのforループを持ち、personがすでに使用されているかどうかを確認することですが、これはおそらく再帰を含むより良い方法があるようです。

誰かが助けてくれるなら、私はとても感謝しています。

これが私のクラスの例です。

public class Calculator {

    final Person[] people = new Person[25]; //Pretend we have filled in this info already

    public List<Group> generateList()
    {
        final List<Group> possible = new ArrayList<>();
        for (int a = 0; a < 25; a++)
        {
            for (int b = 0; b < 25; b++)
            {
                for (int c = 0; c < 25; c++)
                {
                    for (int d = 0; d < 25; d++)
                    {
                        for (int e = 0; e < 25; e++)
                        {
                            final Group next = new Group();
                            next.set = new Person[] {
                                people[a],
                                people[b],
                                people[c],
                                people[d],
                                people[e]
                            };
                            possible.add(next);
                        }
                    }
                }
            }
        }
        return possible;
    }



    class Group {

        Person[] set = new Person[5];

    }

    class Person {

        String name;
        int age;

    }

}

しかし、これを行うための最良の方法はわかりません。それがすべての組み合わせを取得するかどうかもわかりません。また、ここで重複チェックがないことも知っています。これは、チェックすることで行います。

if（b == a）続行;

等。

助けていただければ幸いです。

4

2 に答える 2

9

1つの可能性は、http ：//code.google.com/p/combinatoricslib/のような組み合わせライブラリを使用することです。

// Create the initial vector
   ICombinatoricsVector<String> initialVector = Factory.createVector(
      new String[] { "red", "black", "white", "green", "blue" } );

   // Create a simple combination generator to generate 3-combinations of the initial vector
   Generator<String> gen = Factory.createSimpleCombinationGenerator(initialVector, 3);

   // Print all possible combinations
   for (ICombinatoricsVector<String> combination : gen) {
      System.out.println(combination);
   }

例はプロジェクトページからのものです（リンクを参照）。ユースケースに転送するのは非常に簡単です。

于 2012-12-17T14:53:39.950 に答える
2

多くのオプションがあります。

（1）

を使用してアルゴリズムを改善できます

for a = 0 to 25 
  for b = a+1 to 25  // use ascending-order rule 
    for c = b+1 to 25

など-これにより、問題の階乗の性質を利用して、重複チェックが排除されます

（2）

または、これらをN ^ Rアイテム全体の単一のforループとして実装し（NからRアイテムを選択した場合）、完全な昇順ではない順列を破棄することもできます。これは、事前にRを知らない場合に適しています。ベースNで数えていると想像してください

for i = 0 to N^R // count in base N
  for digit = 0 to R 
    value[digit] = (i/N^digit) mod (N^(digit+1)) // extract the required digit
    if digit>0 && value[digit]<value[digit-1], SKIP

つまり、これらのRインデックスを順番に使用します。

（3）

最後のオプションは、コーディングに時間がかかりますが、大きなRとNの場合はより効率的であり、一連のインデックスを使用することです。

// i is an array size R, with items ranging from 0 to N
i = int[]{ 0, 1, 2, 3, 4 }; // each is an index of the items in N

while !finished
    j=0; // index to start incrementing at
    i[j] ++;

次に、N任意のインデックスで上に移動した場合は、を増やしj、増分し、すべてをi[j]に設定して、もう一度カウントを開始します。これは、すべての組み合わせで最も効率的に循環します。i[k<j][0 1 2 ... j-1]

于 2012-12-17T15:10:06.137 に答える