Java Найти все возможные комбинации из столбцов

Question

У меня есть алгоритм, который возвращает все возможные комбинации, беря по одному пункту из каждого столбца (здесь выбор супа, лапши и начинки).

Есть ли более эффективный и динамичный способ сделать это? Для того, чтобы метод findAllCombinations работал, мне нужно знать, сколько столбцов есть и их жесткий код.

Допустимые комбинации: [кресс суп, удон, Fish Cube], [Пряный суп, Ramen, Ham], ...

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

Если настроить структуру, чтобы быть список наборов вместо список списков, вы можете использовать гуавы-х Sets.cartesianProduct():

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

При заказе важно, вы можете использовать LinkedHashSet.

EDIT: Начиная с версии 19, Guava имеет Lists.cartesianProduct(), что должно делать именно то, что вы хотите.

Answer 2

Если вы не используете Guava и хотите/не хотите катиться самостоятельно, здесь вы идете (код ниже).

Идея состоит в том, чтобы вычислить количество комбинаций как произведение размеров списка, затем перебрать от 0 до number_of_combinations -1 и преобразовать каждое целое число в этом диапазоне в отдельную комбинацию.

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

}