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;

    }

}

但是，我不确定执行此操作的最佳方法，以及是否可以得到所有组合。我也知道这里没有重复检查，我会通过检查来做到这一点；

如果（b == a）继续；

等等。

我将不胜感激任何帮助。

4

2 回答 2

9

一种可能性是使用组合库，例如：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 回答