Java查找列中所有可能的組合

Question

我有一個算法，通過從每列中取出一個項目（這裏是湯，麪條和澆頭的選擇）來返回所有可能的組合。

有沒有一個更有效率和動態的方式來做到這一點？爲了使findAllCombinations方法起作用，我需要知道有多少列並對它們進行硬編碼。

有效組合： [西洋菜湯，烏冬面，魚立方]，[辣湯，拉麪，火腿] ...

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。

編輯：從版本19，番石榴有Lists.cartesianProduct()，這應該做你想要的。

Answer 2

如果你不使用番石榴，需要/想要推出自己的，在這裏你去（代碼如下）。

這個想法是計算組合的數量作爲列表大小的乘積，然後從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"); 
} 

}