Come creare combinazioni di valori in Java?

Question

Ho la seguente mappa: Map<Integer,String[]> map = new HashMap<Integer,String[]>();

Le chiavi sono numeri interi e i valori sono matrici (potrebbero anche essere sostituite da elenchi).

Ora, vorrei ottenere tutte le possibili combinazioni dei valori tra i tasti. Per esempio, diciamo che la mappa contiene le seguenti voci:

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

Le combinazioni consiste di

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

Per questo immagino un metodo boolean hasNext() che restituisce vero se ci sarà una prossima coppia ed un secondo metodo che restituisce solo il prossimo insieme di valori (se presenti).

Come si può fare? La mappa potrebbe anche essere sostituita da un'altra struttura di dati.

Answer 1

L'algoritmo è essenzialmente quasi uguale all'algoritmo di incremento per i numeri decimali ("x -> x + 1").

Qui la classe iteratore:

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

} 

Qui l'utilizzo di esempio:

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

Esso stampa esattamente che cosa sta specificato nel tuo esempio.

---

P.S. La mappa non è effettivamente necessaria; potrebbe essere sostituito da una semplice matrice di matrici (o un elenco di liste). Il costruttore sarebbe quindi ottenere un po 'più semplice:

public CombinationsIterator(final String[][] array) { 
    combinationLength = array.length; 
    values = array; 

    // ... 

    // Reorganize the map to array - THIS CAN BE REMOVED. 

Answer 2

ho preso questo come una sfida per vedere se i nuovi Java 8 API aiutare con questo tipo di problemi. Quindi, ecco la mia soluzione per il problema:

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

Si noti che io non uso una mappa come un ingresso come le chiavi della mappa in realtà non svolgono alcun ruolo qui. È possibile utilizzare map.values() per passare l'input per l'iteratore. Con il seguente codice di prova:

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

l'uscita sarà:

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