How to create value combinations in Java?

Question

I have the following map: Map<Integer,String[]> map = new HashMap<Integer,String[]>();

Keys are integers, and values ​​are arrays (can also be replaced by lists).

Now I would like to get all possible combinations of values ​​between the keys. For example, suppose a card contains the following entries:

 key 1: "test1", "stackoverflow" key 2: "test2", "wow" key 3: "new" 

Combinations consist of

 ("test1","test2","new") ("test1","wow","new") ("stackoverflow", "test2", "new") ("stackoverflow", "wow", "new") 

To do this, I present the boolean hasNext() method, which returns true if there is the next pair and the second method that simply returns the next set of values ​​(if any).

How can I do that? The map can also be replaced with a different data structure.

Answer 1

The algorithm is essentially the same as the increment algorithm for decimal numbers ("x → x + 1").

Here's the iterator class:

 import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.TreeSet; public class CombinationsIterator implements Iterator<String[]> { // Immutable fields private final int combinationLength; private final String[][] values; private final int[] maxIndexes; // Mutable fields private final int[] currentIndexes; private boolean hasNext; public CombinationsIterator(final Map<Integer,String[]> map) { combinationLength = map.size(); values = new String[combinationLength][]; maxIndexes = new int[combinationLength]; currentIndexes = new int[combinationLength]; if (combinationLength == 0) { hasNext = false; return; } hasNext = true; // Reorganize the map to array. // Map is not actually needed and would unnecessarily complicate the algorithm. int valuesIndex = 0; for (final int key : new TreeSet<>(map.keySet())) { values[valuesIndex++] = map.get(key); } // Fill in the arrays of max indexes and current indexes. for (int i = 0; i < combinationLength; ++i) { if (values[i].length == 0) { // Set hasNext to false if at least one of the value-arrays is empty. // Stop the loop as the behavior of the iterator is already defined in this case: // the iterator will just return no combinations. hasNext = false; return; } maxIndexes[i] = values[i].length - 1; currentIndexes[i] = 0; } } @Override public boolean hasNext() { return hasNext; } @Override public String[] next() { if (!hasNext) { throw new NoSuchElementException("No more combinations are available"); } final String[] combination = getCombinationByCurrentIndexes(); nextIndexesCombination(); return combination; } private String[] getCombinationByCurrentIndexes() { final String[] combination = new String[combinationLength]; for (int i = 0; i < combinationLength; ++i) { combination[i] = values[i][currentIndexes[i]]; } return combination; } private void nextIndexesCombination() { // A slightly modified "increment number by one" algorithm. // This loop seems more natural, but it would return combinations in a different order than in your example: // for (int i = 0; i < combinationLength; ++i) { // This loop returns combinations in the order which matches your example: for (int i = combinationLength - 1; i >= 0; --i) { if (currentIndexes[i] < maxIndexes[i]) { // Increment the current index ++currentIndexes[i]; return; } else { // Current index at max: // reset it to zero and "carry" to the next index currentIndexes[i] = 0; } } // If we are here, then all current indexes are at max, and there are no more combinations hasNext = false; } @Override public void remove() { throw new UnsupportedOperationException("Remove operation is not supported"); } } 

Here's a usage example:

 final Map<Integer,String[]> map = new HashMap<Integer,String[]>(); map.put(1, new String[]{"test1", "stackoverflow"}); map.put(2, new String[]{"test2", "wow"}); map.put(3, new String[]{"new"}); final CombinationsIterator iterator = new CombinationsIterator(map); while (iterator.hasNext()) { System.out.println( org.apache.commons.lang3.ArrayUtils.toString(iterator.next()) ); } 

It accurately prints what is indicated in your example.

---

PS The card is not really needed; it can be replaced with a simple array of arrays (or a list of lists). Then the constructor will be a little easier:

 public CombinationsIterator(final String[][] array) { combinationLength = array.length; values = array; // ... // Reorganize the map to array - THIS CAN BE REMOVED. 

Answer 2

I took it as a challenge to see if the new Java 8 APIs help with such problems. So here is my solution to the problem:

 public class CombinatorIterator implements Iterator<Collection<String>> { private final String[][] arrays; private final int[] indices; private final int total; private int counter; public CombinatorIterator(Collection<String[]> input) { arrays = input.toArray(new String[input.size()][]); indices = new int[arrays.length]; total = Arrays.stream(arrays).mapToInt(arr -> arr.length) .reduce((x, y) -> x * y).orElse(0); counter = 0; } @Override public boolean hasNext() { return counter < total; } @Override public Collection<String> next() { List<String> nextValue = IntStream.range(0, arrays.length) .mapToObj(i -> arrays[i][indices[i]]).collect(Collectors.toList()); //rolling carry over the indices for (int j = 0; j < arrays.length && ++indices[j] == arrays[j].length; j++) { indices[j] = 0; } counter++; return nextValue; } } 

Please note that I do not use the map as input, since in fact the map keys do not play any role. You can use map.values() though to pass input to an iterator. With the following test code:

 List<String[]> input = Arrays.asList( new String[] {"such", "nice", "question"}, new String[] {"much", "iterator"}, new String[] {"very", "wow"} ); Iterator<Collection<String>> it = new CombinatorIterator(input); it.forEachRemaining(System.out::println); 

the output will be:

 [such, much, very] [nice, much, very] [question, much, very] [such, iterator, very] [nice, iterator, very] [question, iterator, very] [such, much, wow] [nice, much, wow] [question, much, wow] [such, iterator, wow] [nice, iterator, wow] [question, iterator, wow]