生成所有可能的组合 - Java
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/37835286/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generate All Possible Combinations - Java
提问by Maddy
I have a list of items {a,b,c,d} and I need to generate all possible combinations when,
我有一个项目列表 {a,b,c,d} 并且我需要在以下情况下生成所有可能的组合，
- you can select any number of items
- the order is not important (ab = ba)
- empty set is not considered
- 您可以选择任意数量的项目
- 顺序不重要（ab = ba）
- 不考虑空集
If we take the possibilities, it should be,
如果我们考虑可能性，它应该是，
n=4, number of items
total #of combinations = 4C4 + 4C3 + 4C2 + 4C1 = 15
I used the following recursive method:
我使用了以下递归方法：
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);
}
}
Is there a more efficient way of doing this when the array size is large?
当数组很大时，有没有更有效的方法来做到这一点？
回答by yash sachdeva
Consider the combination as a binary sequence, if all the 4 are present, we get 1111 , if the first alphabet is missing then we get 0111, and so on.So for n alphabets we'll have 2^n -1 (since 0 is not included) combinations.
将组合视为一个二进制序列，如果所有 4 个都存在，我们得到 1111 ，如果第一个字母丢失，那么我们得到 0111，依此类推。所以对于 n 个字母，我们将有 2^n -1（因为 0不包括在内）组合。
Now, in your binary sequence produced, if the code is 1 , then the element is present otherwise it is not included. Below is the proof-of-concept implementation:
现在，在您生成的二进制序列中，如果代码为 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();
}
And here's a generic reusable implementation:
这是一个通用的可重用实现：
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);
}
