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

如果您将结构调整为集合列表，而不是列表列表，则可以使用Guava的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

如果您不使用Guava，并且需要/想要使用自己的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");
}

}