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

}