-1

这个问题很难用一句话来解释，而且我似乎也找不到一个好的，简单的方法来做。我要问的是：如果我有一个数字列表（数组）（也可以是字符串），假设数字最多为 7，并且我想选择 5 个数字，所有这些数字都不同，我将如何找到所有五个数字的不同组合，并将它们保存在一个数组中。

例如，我有一个 7 个数字的列表。我只能使用 5 个不同的数字。我的组合是：

1. 1 2 3 4 5
2. 1 2 3 4 6
3. 1 2 3 4 7
4. 1 2 3 5 6
5. 1 2 3 5 7

等等

我如何编写一个 java 程序，将所有这些组合放在一个数组中。解释也将不胜感激。

4

2 回答 2

0

我不会为您提供完整的解决方案，因为这对任何人都没有帮助，而是对初始解决方案的一些建议（不一定是最佳解决方案）

到目前为止，最简单的做法是创建任意长度的所有组合并消除所有长度不为 5 的组合。您可以通过检查输入的每个数字并确定是否包含它来做到这一点，并且跟踪您有多少包含的数字；如果最后没有 5 个数字，则拒绝该组合。

这样做的天真方法是嵌套 for 循环

for(int i=0;i<2;i++){
    //either include the first or not depending on if i is 0 or 1
    for(int j=0;j<2;j++){
          //either include the first or not depending on if i is 0 or 1
          for(........
             ..........
                 built the combination and if its length 5 add it to a collection
          } 
    } 
}

这当然是对原始输入大小的大小进行硬编码；这可以避免使用将combinationObject正在构建的a 作为参数的递归函数，inputNumbers以及当前递归深度（因此它知道要决定哪个输入数字。它会返回一些集合（例如 hashset 或 arraylist）将是在递归方面“低于”它生成的所有集合的总和（在每个级别，函数将调用自身两次；一次用于包含，一次用于不包含。

这个递归函数看起来像

public Collection<CombinationObject> addDigit(CombinationObject combinationSoFar, InputObject numbersToChooseFrom, int depth){
      if (depth==numbersToChooseFrom.size()){
           Collection<CombinationObject> collection=new HashSet<CombinationObject>();
           collection.add(combinationSoFar.add(numbersToChooseFrom.get(depth); //add a digit
           collection.add(combinationSoFar); //don't add a digit

           return collection;
      }else{
           Collection<CombinationObject> collection=new HashSet<CombinationObject>();
           collection.addAll(addDigit(combinationSoFar.add(InputObject.getDigit(depth), InputObject numbersToChooseFrom,depth+1);
           collection.addAll(addDigit(combinationSoFar, InputObject numbersToChooseFrom,depth+1);
           return collection;
      }
}

NB。combinationSoFar 应该是不可变的，并且 .add 方法应该返回一个新对象

就效率而言，这可能不是一个理想的解决方案，但希望能帮助您入门

于 2013-09-03T09:47:50.683 回答
0

你可以使用递归来做到这一点（不是我经常说的）

public static <T> void combinations(List<T> values, int maxCount, CombinationListener<T> listener) {
    List<T> comb = (List<T>) Arrays.asList(new Object[maxCount]);
    boolean[] used = new boolean[values.size()];
    combinations0(values, used, comb, 0, maxCount, listener);

}

static <T> void combinations0(List<T> values, boolean[] used, List<T> comb, int idx, int maxCount, CombinationListener<T> listener) {
    if (idx == maxCount) {
        listener.onComlination(comb);
        return;
    }
    for (int i = 0; i < values.size(); i++) {
        if (used[i]) continue;

        used[i] = true;
        comb.set(idx, values.get(i));
        combinations0(values, used, comb, idx + 1, maxCount, listener);
        used[i] = false;
    }
}

public static void main(String[] args) {
    combinations(Arrays.asList(1, 2, 3, 4, 5, 6, 7), 5, new CombinationListener<Integer>() {
        @Override
        public void onComlination(List<Integer> list) {
            System.out.println(list);
        }
    });
}

interface CombinationListener<T> {
    void onComlination(List<T> list);
}

印刷

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 6]
[1, 2, 3, 4, 7]
[1, 2, 3, 5, 4]
[1, 2, 3, 5, 6]
[1, 2, 3, 5, 7]
[1, 2, 3, 6, 4]
[1, 2, 3, 6, 5]
[1, 2, 3, 6, 7]
... many deleted ...
[7, 6, 5, 2, 4]
[7, 6, 5, 3, 1]
[7, 6, 5, 3, 2]
[7, 6, 5, 3, 4]
[7, 6, 5, 4, 1]
[7, 6, 5, 4, 2]
[7, 6, 5, 4, 3]
于 2013-09-03T10:15:39.817 回答