As the title indicates, I am looking for a solution on how to implement the getNextCombination method shown in the code snippet below.

public class Test {

    private final List<List<String>> iterators;
    
    /**
     * @return null if no combination left
     */
    public String[] getNextCombination() {
        return null;
    }
}

Assuming the attribute iterator would look like

[0]={1,2} 
[1]={4,5} 
[2]={7,8}

then the sequential call to the getNextCombination method should return something similar to this:

147
148
157
158
247
248
...
NULL

How can this be achieved as efficient as possible?

Thanks for any help.

CodePudding user response：

You can do something like this :

private final List<List<String>> iterators = Arrays.asList(Arrays.asList("1", "2"), Arrays.asList("4", "5"), Arrays.asList("7", "8"));

public void run() {
    one("", 0, 0, iterators.size(), iterators.get(0).size()); // begin the iterate over
}

public void iterateOver(String before, int x, int y, int maxX, int maxY) {
    List<String> secondList = iterators.get(x); // get Y value list
    secondList.forEach((ss) -> {
        if(x   1 < maxX) { // go to next line
            iterateOver(before   ss, x   1, 0, maxX, iterators.get(x   1).size());
        } else if(y   1 < maxY) {
            System.out.println(before   ss); // print result
            iterateOver(before   ss, x, y   1, maxX, maxY); // go to next Y value
        } else {
            // this is finished
        }
    });
}

Output:

147
148
157
158
247
248
257
258

Warns: Arrays#asList list are not editable.

Also, I didn't make the full getNextCombination method because now you can use this code as you want to implement your prefered way to be at a combination, and go to next.

CodePudding user response：

The following generic lazy function to calculate all combinations do the job and works for any number of lists or any other structure

static Stream<int []> combinationsStream(final int... numElems) {
    final int numCombinations = Arrays.stream(numElems)                 // the number of solutions is
            .map(n -> n   1)                                            // possibles sizes
            .reduce(1, (a, b) -> a * b);                                // product

    final int[] queue = Arrays.stream(numElems).map(i -> -1).toArray(); // for every item take n elements
    final int[] i = new int[]{0};                                       // volatile (final) integer
    final Function<int [], int []> next = o -> {                        // compute the next combination
        while (true) {
            if (i[0] == numElems.length) {                              // if is the last position
                i[0] -= 1;                                              // we will back
                return queue;                                           // but it's a combination
            }
            queue[i[0]]  = 1;                                           // take one more of i[0]-th element
            if (queue[i[0]] > numElems[i[0]])                           // if no more of this
                queue[i[0]--] = -1;                                     // reset and go back
            else
                i[0]  = 1;                                              // if not, go forward
        }
    };
    return Stream.iterate(null, next::apply)                            // iterate getting next over and over
            .skip(1)                                                    // avoid the seed (null)
            .limit(numCombinations);                                    // limit the stream to combs number
}

since only work with indexes, you can use as follows

Let your list:

// let you list of list (from somewhere)
List<List<String>> iterators = asList(
        asList("1", "2"),
        asList("4", "5"),
        asList("7", "8")
);

(lists could contains different number of elements)

then, to get a lazy stream with all combinations simply convert the list of list to an array of max indexes

// we get combinations in a lazy way simply with
// (you could set this stream in your private class field if you wish)
Stream<int []> lazyCombinations = combinationsStream(iterators.stream()
        .mapToInt(g -> g.size() - 1).toArray());

in your case the call will be combinationsStream(1, 1, 1) since valid indexes are 0, 1 for each list.

To convert some index combination to your String output get the indexes and join

// to convert the indexes array to values (and concatenate all) you can write the function
Function<int [], String> toString = indexes -> IntStream
        // for each list
        .range(0, indexes.length)
        // get the indexes[i]-th element
        .mapToObj(i -> iterators.get(i).get(indexes[i]))
        // and join
        .collect(joining());

then, simply map the previous Stream<int []> to Stream<String> using that function

// now you can convert your indexes stream to your final combinations stream (all lazy)
Stream<String> lazySolutions = lazyCombinations.map(toString);

you can use the Stream in many ways (i.e. return in a Web Service lazily) but, if you wish take one by one you can convert to an iterator.

The itarator is lazy too

// if you need peek combinations on demand (not in a streaming way) convert stream to iterator
Iterator<String> lazyIterator = lazySolutions.iterator();

Then, you can take only one

// you can take one by one (e.g. inside a `getNextCombination`)
System.out.println("Only one: "   lazyIterator.next());

or as many as you consider

// or to the end
lazyIterator.forEachRemaining(System.out::println);

with output

Only one: 147
148
157
158
247
248
257
258