生成所有可能的组合 - Java

Question

我有一个项目列表{a,b,c,d}，需要生成所有可能的组合，其中：

• 您可以选择任意数量的项目
• 顺序不重要（ab = ba）
• 空集不被考虑

如果我们考虑这些可能性，则应该是：

n=4, number of items
total #of combinations = 4C4 + 4C3 + 4C2 + 4C1 = 15

我使用了以下递归方法：

private void countAllCombinations (String input,int idx, String[] options) {
    for(int i = idx ; i < options.length; i++) {
        String output = input + "_" + options[i];
        System.out.println(output);
        countAllCombinations(output,++idx, options);
    }
}

public static void main(String[] args) {
    String arr[] = {"A","B","C","D"};
    for (int i=0;i<arr.length;i++) {
        countAllCombinations(arr[i], i, arr);
    }
}

当数组大小较大时，有没有更有效的方法来完成这个任务？

- Maddy

---

这是一种指数级算法，因此对于大型数组，无论如何速度都会很慢。 - Kayaman

你可以查看https://dev59.com/8WEi5IYBdhLWcg3w0O6Q和https://dev59.com/5WUp5IYBdhLWcg3wHkyo?s=4|0.0000。 - Tunaki

是的，还有更有效的方法。在这里（指 Stack Overflow）有现成的解决方案，可以从大小为N的列表中生成大小为M的子集，以及对子集进行排列组合。将它们结合起来就可以实现你想要的功能。 - AdamSkywalker

еңЁжӮЁзҡ„жғ…еҶөдёӢпјҢз»„еҗҲж•°йҮҸдёәJavaдёӯзҡ„Math.pow(2,n)-1пјҢе…¶дёӯnжҳҜжӮЁзҡ„ж•°з»„еӨ§е°ҸгҖӮ - jr593

“duplicate”链接是一个更加复杂、不同的问题。 - Alex R

Answer 1

考虑将组合视为二进制序列，如果四个都存在，则得到1111，如果缺少第一个字母，则得到0111，依此类推。因此，对于n个字母，我们将有2^n-1（因为0不包括在内）种组合。

现在，在生成的二进制序列中，如果代码为1，则该元素存在，否则不包括在内。下面是概念验证实现：

String arr[] = { "A", "B", "C", "D" };
int n = arr.length;
int N = (int) Math.pow(2d, Double.valueOf(n));  
for (int i = 1; i < N; i++) {
    String code = Integer.toBinaryString(N | i).substring(1);
    for (int j = 0; j < n; j++) {
        if (code.charAt(j) == '1') {
            System.out.print(arr[j]);
        }
    }
    System.out.println();
}

这里有一个通用的可重复使用的实现：

public static <T> Stream<List<T>> combinations(T[] arr) {
    final long N = (long) Math.pow(2, arr.length);
    return StreamSupport.stream(new AbstractSpliterator<List<T>>(N, Spliterator.SIZED) {
        long i = 1;
        @Override
        public boolean tryAdvance(Consumer<? super List<T>> action) {
            if(i < N) {
                List<T> out = new ArrayList<T>(Long.bitCount(i));
                for (int bit = 0; bit < arr.length; bit++) {
                    if((i & (1<<bit)) != 0) {
                        out.add(arr[bit]);
                    }
                }
                action.accept(out);
                ++i;
                return true;
            }
            else {
                return false;
            }
        }
    }, false);
}

- yash sachdeva