How to recursively get all combinations in Java?

Question

What is the best way in Java to make recursive function to get all combinations of elements taken from several sets of candidates?

In general the number of candidate sets is undefined so recursive solution seems to be appropriate for this task. As an example for given sets of candidates

[1,2]
[3,4]
[5,6,7]

should get 12 combinations:

[1,3,5] [2,3,5] 
[1,4,5] [2,4,5]
[1,3,6] [2,3,6]
[1,4,6] [2,4,6]
[1,3,7] [2,3,7]
[1,4,7] [2,4,7] 

Candidate set is represented as List of List of Type: List<List<T>>

Answer 1

And here's another version (Odometer, as Andy Thomas suggested)

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Odometer<T> implements Iterable<List<T>> {

    private class Wheel {
        List<T> values;
        int         idx = 0;

        /**
         * Create an odometer wheel from list of values
         * @param v
         */
        protected Wheel (List<T> v) {
            if (v == null)   throw new NullPointerException("can't create an instance of Wheel.class with null values");
            if (v.isEmpty()) throw new IllegalArgumentException("can't create an instance of Wheel.class with no values");
            this.values = v;
        }

        /**
         * Get wheel value
         * @return
         */
        protected T value() {
            return values.get(idx);
        }

        /**
         * switch an odometer wheel one step 
         * @return TRUE - if a wheel have made full cycle and have switched to first item
         */
        protected boolean next() {
            if (idx >= values.size() - 1) {
                idx = 0; 
                return true;
            } else {
                idx++;
                return false;
            }

        }
    }

    /**
     * list of wheels
     */
    private List<Wheel> wheels = new ArrayList<Wheel>();

    /**
     * Create an odometer from several lists of values 
     * (each List<T> is a list of values for one odometer wheel)
     * @param values
     */
    public Odometer(List<List<T>> values) {
        for (List<T> v : values)
            wheels.add(new Wheel(v));
    }

    /**
     * Get odometer value
     * @return
     */
    public List<T> get() {
        List<T> result = new ArrayList<T>();
        for (Wheel wheel : wheels) {
            result.add(wheel.value());
        }
        return result;
    }

    /**
     * Switch to next value
     * @return TRUE if full cycle is finished
     */
    public boolean next() {
        for (int i = wheels.size() - 1; i >= 0; i--)
            if (!wheels.get(i).next()) return false;
        return true;
    }

    /**
     * Reset odometer
     */
    public void reset() {
        for (Wheel wheel : wheels)
            wheel.idx = 0;
    }

    /**
     * Iterator
     */
    @Override
    public Iterator<List<T>> iterator() {
        reset();
        Iterator<List<T>> it = new Iterator<List<T>>() {
            private boolean last = false;

            @Override
            public boolean hasNext() {
                return !last;
            }
            @Override
            public List<T> next() {
                List<T> result = get();
                last = Odometer.this.next();
                return result;
            }
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
        return it;  
    }

    public static void main(String [] args) {
        List<Integer> l1 = new ArrayList<Integer>(); l1.add(1); l1.add(2);
        List<Integer> l2 = new ArrayList<Integer>(); l2.add(3); l2.add(4); l2.add(5);
        List<Integer> l3 = new ArrayList<Integer>(); l3.add(6); l3.add(7);
        List<List<Integer>> list = new ArrayList<List<Integer>>(); list.add(l1); list.add(l2); list.add(l3); 
        Odometer<Integer> odometer = new Odometer<Integer>(list);
        for (List<Integer> value : odometer) {
            System.out.println(value);
        }
    }
}

Answer 2

Thank you all for your replies.

Andy Thomas, quite interesting idea with odometer. Will give it a try a bit later. For now I've implemented it as ThatOneCloud suggested.

Here's what i've got (for Integer items; if needed can be generalized):

public List<List<Integer>> makeCombinations(List<List<Integer>> candidates) {

    List<List<Integer>> result = new ArrayList<List<Integer>>();

    // calculate result size
    int size = 1;
    for (List<Integer> candidateSet : candidates)
        size *= candidateSet.size();

    // make result
    for (int i = 0; i < size; i++)
        result.add(new ArrayList<Integer>());

    // fill result
    int pos = 1;
    for (List<Integer> candidateSet : candidates)
        fillPosition(candidateSet, result, countRepeats(candidates, pos++));

    // return
    return result;
}

public int countRepeats(List<List<Integer>> candidates, int pos) {

    int repeats = 1;
    for (int i = pos; i < candidates.size(); i++)
        repeats *= candidates.get(i).size();
    return repeats;
}

public void fillPosition(   List<Integer>      candidateSet, 
                            List<List<Integer>>      result, 
                            int                     repeats) {

    int idx = 0;
    while (idx < result.size()) {
        for (int item : candidateSet) {
            for (int i = 0; i < repeats; i++) {
                result.get(idx++).add(item);
            }
        }
    }
}

Answer 3

I encountered this same problem several years ago. I solved it by iterating through the result list with an odometer.

The number of wheels in the odometer is the number of input sets. The figures on each wheel are the members of the corresponding set. To get the next permutation, roll the rightmost odometer wheel. If it's turned all the way around, roll the one to it's left, etc.

For example:

Wheel 0 values: [1,2]
Wheel 1 values: [3,4]
Wheel 2 values: [5,6,7]

Start with odometer reading (1,3,5). Advance to (1,3,6), (1,3,7). Then roll the next wheel as well, to (1,4,5), (1,4,6) and (1,4,7). Continue.

Odometer wheels as indices

Alternatively, you can represent the wheels as indices into the corresponding list.

Wheel 0 values: [0,1]
Wheel 1 values: [0,1]
Wheel 2 values: [0,1,2]

Start with odometer reading (0,0,0). Advance to (0,0,1), (0,0,2). Then roll the next wheel as well, to (0,1,0), (0,1,1) and (0,1,2). Continue. For each reading, translate to the result list by using the odometer wheel readings as indices into the input lists.

Odometer wheels as iterators

As another alternative, you can represent the wheels as iterators into the input collections. This is more general than the prior two approaches. It works even if the input collections are not accessible by index. And it's scalable. And this is the approach I used several years ago.

Answer 4

The total number of combinations is the product of the sizes of the candidate sets. Each result set's size is equal to the number of candidate sets.

You don't need recursion for the solution. Just go through each candidate set. In this example, the first has two values, 1 and 2. The first 6 result sets (half of them) get the first value as 1. The next half get 6.

Onto the next candidate set, there are two values, 3 and 4. But this time, alternate assigning them in groups of 3, rather than 6. So the first 3 result sets get 3, the next 3 sets get 4, the next 3 get 3, and so on.

The next candidate set has three values: 5, 6, and 7. You'll be rotating which value you assign for each result set now (rotating each 1 assignment.) If there were more candidate sets or different amounts of values in them, the amount you assign before rotating to the next value would change. But you can figure this out programatically.

Answer 5

You don't need recursion. Just use the size of the list of sets and then of each set. You can keep the results open to addition of further elements, in case you get more sets to mix in in the future, in case that's what you need.