Java Finden Sie alle möglichen Kombinationen aus Spalten

Question

Ich habe einen Algorithmus, der alle möglichen Kombinationen zurückgibt, indem Sie ein Element aus jeder Spalte (Hier eine Auswahl von Suppe, Nudeln und Belag).

Gibt es einen effizienteren und dynamischeren Weg dies zu tun? Damit die findAllCombinations-Methode funktioniert, muss ich wissen, wie viele Spalten vorhanden sind, und sie fest codieren.

Gültige Kombinationen: [Kressesuppe, Udon, Fisch Cube], [würzige Suppe, Ramen, Schinken], ...

ArrayList<ArrayList<String>> listOfLists = Lists.newArrayList(); 
listOfLists.add(Lists.newArrayList("Original Soup", "Spicy Soup", "Watercress Soup", "Thai Spicy Soup", "Malaysia Spicy Soup")); 
listOfLists.add(Lists.newArrayList("Udon", "Ramen", "Egg Noodle", "Flat Rice Noodle", "Vermicelli", "Instant Noodle")); 
listOfLists.add(Lists.newArrayList("Fish Cube", "Fish Ball", "Ham", "Squid", "Seaweed")); 

ArrayList<ArrayList<String>> combo = findAllCombinations(listOfLists); 


private ArrayList<ArrayList<String>> findAllCombinations(ArrayList<ArrayList<String>> arrays){ 
    ArrayList<ArrayList<String>> combinations = new ArrayList<>(); 
    for(String item1: arrays.get(0)){ 
     for(String item2: arrays.get(1)){ 
      for(String item3: arrays.get(2)){ 
       ArrayList<String> temp = new ArrayList<String>() { 
        { 
         add(item1); 
         add(item2); 
         add(item3); 
        } 
       }; 
       combinations.add(temp); 
      } 
     } 
    } 
    return combinations; 
} 

Answer 1

Wenn Sie Ihre Struktur zwicken eine Liste von Sätzen sein statt eine Liste der Listen können Sie Guava der Sets.cartesianProduct() verwenden:

List<Set<String>> listOfSets = Lists.newArrayList(); 
listOfSets.add(Sets.newHashSet("Original Soup", "Spicy Soup", "Watercress Soup", "Thai Spicy Soup", "Malaysia Spicy Soup")); 
listOfSets.add(Sets.newHashSet("Udon", "Ramen", "Egg Noodle", "Flat Rice Noodle", "Vermicelli", "Instant Noodle")); 
listOfSets.add(Sets.newHashSet("Fish Cube", "Fish Ball", "Ham", "Squid", "Seaweed")); 

Set<List<String>> combo = Sets.cartesianProduct(listOfSets); 

Wenn Bestellung wichtig ist, Sie LinkedHashSet verwenden können.

EDIT: Ab Version 19 hat Guava Lists.cartesianProduct(), die genau das tun sollten, was Sie wollen.

Answer 2

Wenn Sie Guava nicht benutzen und Ihre eigenen rollen wollen/wollen, gehen Sie hier (Code unten).

Die Idee besteht darin, die Anzahl der Kombinationen als das Produkt der Listengrößen zu berechnen, dann von 0 bis number_of_combinations -1 zu iterieren und jede ganze Zahl in diesem Bereich in eine eindeutige Kombination zu konvertieren.

import java.util.ArrayList; 
import java.util.Arrays; 

public class Tester { 

private static ArrayList<ArrayList<String>> findAllCombinations(ArrayList<ArrayList<String>> arrays){ 
    final ArrayList<ArrayList<String>> combinations = new ArrayList<>(); 
    int combinationCount = 1; 
    for (final ArrayList<String> als : arrays) { 
     combinationCount *= als.size(); 
    } 

    for (int i = 0; i < combinationCount; i++) { 
     int combinationIndex = i; 
     final ArrayList<String> oneCombination = new ArrayList<String>(); 
     for (final ArrayList<String> als : arrays) { 
      int index = combinationIndex % als.size(); 
      oneCombination.add(als.get(index)); 
      combinationIndex = (combinationIndex - index)/als.size(); 
     } 
     combinations.add(oneCombination); 
    } 
    return combinations; 
} 

public static void main(String[] args) { 

final ArrayList<ArrayList<String>> listOfLists = new ArrayList<ArrayList<String>>(); 
listOfLists.add(new ArrayList<String>(Arrays.asList(new String[] {"Original Soup", "Spicy Soup", "Watercress Soup", "Thai Spicy Soup", "Malaysia Spicy Soup"}))); 
listOfLists.add(new ArrayList<String>(Arrays.asList(new String[] {"Udon", "Ramen", "Egg Noodle", "Flat Rice Noodle", "Vermicelli", "Instant Noodle"}))); 
listOfLists.add(new ArrayList<String>(Arrays.asList(new String[] {"Fish Cube", "Fish Ball", "Ham", "Squid", "Seaweed"}))); 

ArrayList<ArrayList<String>> combo = findAllCombinations(listOfLists); 
System.out.println(combo); 
System.out.println("Generated " + combo.size() + " combinations"); 
} 

}