Generate All Possible Combinations - Java

Question

I have a list of items {a,b,c,d} and I need to generate all possible combinations when,

you can select any number of items
the order is not important (ab = ba)
empty set is not considered

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?

It's an exponential algorithm, so for *large* arrays it'll still be slow no matter what. — Kayaman, Jun 15 '16 at 12:23
You can look at http://stackoverflow.com/questions/20935315/java-generate-the-power-set-of-a-given-list and http://stackoverflow.com/questions/15498281/generating-power-set-recursively-without-any-loops?s=4|0.0000 — Tunaki, Jun 15 '16 at 12:26
yes, there are more efficient ways. there are ready solutions (here on stack) for generating subsets of size M from list of size N and for permutations of a subsets. combination of them will do what you want. — AdamSkywalker, Jun 15 '16 at 12:26
In your case the number of combinations is in java `Math.pow(2,n)-1` where `n` is the size of your array — jr593, Jun 15 '16 at 12:59
the linked "duplicate" is a much more complex, different question — Alex R, Dec 01 '19 at 01:55

score 21 · Accepted Answer · edited Dec 01 '19 at 01:51

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.

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:

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);
}

Generate All Possible Combinations - Java

1 Answers1

Linked