Jak tworzyć kombinacje wartości w Javie?

Question

Mam następującą mapę: Map<Integer,String[]> map = new HashMap<Integer,String[]>();

Klucze są liczbami całkowitymi, a wartościami są tablice (można je również zastąpić listami).

Teraz chciałbym uzyskać wszystkie możliwe kombinacje wartości między kluczami. Na przykład, powiedzmy, że mapa zawiera następujące wpisy:

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

The kombinacje składa

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

za to sobie wyobrazić sposób boolean hasNext() która zwraca true, jeśli istnieje następna para i druga metoda która po prostu zwraca następny zestaw wartości (jeśli taki istnieje).

Jak można tego dokonać? Mapę można również zastąpić inną strukturą danych.

Answer 1

Algorytm to w zasadzie prawie taki sam jak algorytm przyrostowy dla liczb dziesiętnych ("x -> x + 1").

Tutaj klasa iterator:

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"); 
    } 

} 

Tutaj wykorzystaniem próbek:

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()) 
    ); 
} 

drukuje dokładnie to, co podano w przykładzie.

---

P.S. Mapa właściwie nie jest potrzebna; można go zastąpić prostą tablicą tablic (lub listą list). Konstruktor będzie wtedy nieco prostszy:

Answer 2

Zrobiłem to jako wyzwanie, aby sprawdzić, czy nowe API Java 8 pomagają w tego typu problemach. Więc oto moje rozwiązanie problemu:

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; 
    } 
} 

Zauważ, że nie używam mapy jako wejście jako klucze map faktycznie nie odgrywają żadnej roli tutaj. Można jednak użyć parametru map.values(), aby przekazać dane wejściowe dla iteratora. Z następującego kodu testu:

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); 

wyjście będzie:

[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]