Java: Combinations of arrays, x per array

You've hit on an overly complicated solution which, nonetheless, just happens to work for the case of two buckets. However, as you have discovered, it won't extend naturally to three or more buckets.

Here's a simpler solution for the two-bucket case, generified and using Lists in place of arrays:

// Find all 2-item combinations consisting of 1 item picked from 
// each of 2 buckets
static <T> List<List<T>> pick1From2(List<List<T>> in)
{
    List<List<T>> result = new ArrayList<>();
    for (int i = 0; i < in.get(0).size(); ++i) {
        for (int j = 0; j < in.get(1).size(); ++j) {
            result.add(Arrays.asList(in.get(0).get(i), in.get(1).get(j)));
        }
    }
    return result;
}

The outer loop runs over all the elements of the first bucket and for each element of the first bucket, the inner loop runs over the elements of the second bucket.

For three buckets, you can just add a third level of loop nesting:

// Find all 3-item combinations consisting of 1 item picked from
// each of 3 buckets 
static <T> List<List<T>> pick1From3(List<List<T>> in)
{
    List<List<T>> result = new ArrayList<>();
    for (int i = 0; i < in.get(0).size(); ++i) {
        for (int j = 0; j < in.get(1).size(); ++j) {
            for (int k = 0; k < in.get(2).size(); ++k)
                result.add(Arrays.asList(in.get(0).get(i), in.get(1).get(j), in.get(2).get(k)));
        }
    }
    return result;
}

Now you have the outer loop stepping through the items of the first bucket, an intermediate loop stepping through the items of the second bucket, and an innermost loop stepping over the elements of the third bucket.

But this approach is limited by the fact that the depth of loop nesting needed is directly related to the number of buckets to be processed: Sure, you can add a fourth, a fifth, etc., level of loop nesting to handle four, five, or more buckets. However, the basic problem remains: you have to keep modifying the code to accommodate ever-increasing numbers of buckets.

The solution to the dilemma is a single algorithm which accommodate any number, N, of buckets by effectively simulating for loops nested to N levels. An array of N indices will take the place of the N loop control variables of N nested for statements:

// Find all `N`-item combinations consisting 1 item picked from 
// each of an `N` buckets
static <T> List<List<T>> pick1fromN(List<List<T>> s)
{
    List<List<T>> result = new ArrayList<>();
    int[] idx = new int[s.size()];
    while (idx[0] < s.get(0).size()) {
        List<T> pick = new ArrayList(s.size());
        for (int i = 0; i < idx.length; ++i) {
            pick.add(s.get(i).get(idx[i]));
        }
        result.add(pick);
        int i = idx.length - 1;
        while (++idx[i] >= s.get(i).size() && i > 0) {
            idx[i] = 0;
            --i;
        }
    }
    return result;
}

The indices all start off at zero, and each maxxes out upon reaching the size of the corresponding bucket. To step to the next combination (inner while loop) the last index index is incremented; if it has maxxed out, it is reset to zero and the next higher index is incremented. If the next higher index also maxes out, it resets and causes the next index to increment, and so on. idx[0] never resets after it increments, so that the outer while can detect when idx[0] has maxxed out.

Picking k items from each bucket is basically the same process, except with the sets of k-combinations of the buckets substituted for the original buckets:

// Find all `N * k`-item combinations formed by picking `k` items
// from each of `N` buckets
static <T> List<List<T>> pickKfromEach(List<List<T>> sets, int k)
{
    List<List<List<T>>> kCombos = new ArrayList<>(sets.size());
    for (List<T> ms : sets) {
        kCombos.add(combinations(ms, k));
    }
    ArrayList<List<T>> result = new ArrayList<>();
    int[] indices = new int[kCombos.size()];
    while (indices[0] < kCombos.get(0).size()) {
        List<T> pick = new ArrayList<>(kCombos.size());
        for (int i = 0; i < indices.length; ++i) {
            pick.addAll(kCombos.get(i).get(indices[i]));
        }
        result.add(pick);
        int i = indices.length - 1;
        while (++indices[i] >= kCombos.get(i).size() && i > 0) {
            indices[i] = 0;
            --i;
        }
    }
    return result;
}

static <T> List<List<T>> combinations(List<T> s, int k) throws IllegalArgumentException
{
    if (k < 0 || k > s.size()) {
        throw new IllegalArgumentException("Can't pick " + k
            + " from set of size " + s.size());
    }
    List<List<T>> res = new LinkedList<>();
    if (k > 0) {
        int idx[] = new int[k];
        for (int ix = 0; ix < idx.length; ++ix) {
            idx[ix] = ix;
        }
        while (idx[0] <= s.size() - k) {
            List<T> combo = new ArrayList<>(k);
            for (int ix = 0; ix < idx.length; ++ix) {
                combo.add(s.get(idx[ix]));
            }
            res.add(combo);
            int ix = idx.length - 1;
            while (ix > 0 && (idx[ix] == s.size() - k + ix))
               --ix;
            ++idx[ix];
            while (++ix < idx.length)
                idx[ix] = idx[ix-1]+1;
        }
    }
    return res;
}

Like the pick routine, the combinations method uses an array of indices to enumerate the combinations. But the indices are managed a bit differently. The indices start out at {0, 1, 2, ..., k-1_}, and they max-out when they have reached the values {n - k, n - k + 1, ..., n}. To step to the next combination, last index which has not yet maxed-out is incremented, and then each following index is reset to the value of the one above it, plus one.