Generate all possible combinations-Java

Question

I have a list of items {a,b,c,d} and I need to generate all the 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?

Answer 1

You can try this using 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);

}

Want to learn Java? Check out the Java certification from intellipaat.