Java Find All Possible Combinations From Columns

Question

I have an algorithm that returns all possible combinations by taking one item from each column (Here a choice of soup, noodles and toppings).

Is there a more efficent and dynamic way to do this? For the findAllCombinations method to work, I need to know how many columns there are and hard code them.

Valid Combinations: [Watercress Soup, Udon, Fish Cube], [Spicy Soup, 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;
}

Why are you skipping the first member of the second array and the first 2 members of the third array? — LostAndConfused, May 31 '16 at 22:22
@LostAndConfused he isn't, he is selecting the first, second and third array — TheBakker, May 31 '16 at 22:30
LOLOLOLOLOL. Thank you. Not sure what happened to me. :) The thought of not having Udon as an option terrified me past the point of logic and reason. :O :D — LostAndConfused, May 31 '16 at 23:02

shmosel · Answer 1 · 2016-05-31T22:47:38.187

2

If you tweak your structure to be a list of sets instead of a list of lists, you can use Guava's 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);

If ordering is important, you can use LinkedHashSet.

EDIT: As of version 19, Guava has Lists.cartesianProduct(), which should do exactly what you want.

edited May 31 '16 at 22:47

answered May 31 '16 at 22:38

shmosel

49,289
6
73
138

I'm not sure on what you mean by using LinkedHashSet. – PandaTank Jun 01 '16 at 00:03
`LinkedHashSet listOfSets = new LinkedHashSet();` will not work. – PandaTank Jun 01 '16 at 00:04
@PandaTank I mean like `listOfSets.add(new LinkedHashSet<>(Arrays.asList("Fish Cube", "Fish Ball", "Ham", "Squid", "Seaweed")));` – shmosel Jun 01 '16 at 00:08

score 2 · Answer 2 · answered May 31 '16 at 22:45

If you don't use Guava and need/want to roll your own, here you go (code below).

The idea is to compute the number of combinations as the product of the list sizes, then iterate from 0 to number_of_combinations-1, and convert each integer in that range to a distinct combination.

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

}

Yes, I know. But based on the title of the post, maybe not everyone who finds this question via search is using Guava. I can delete or revise my answer if that's a StackOverflow "foul". — Matthew McPeak, May 31 '16 at 22:50
No problem with your answer (other than it being more complicated than OP's solution); I was just commenting on your first sentence. Side note: 1) `Arrays.asList()` accepts varargs, and 2) passing its result to a `new ArrayList` is a bit excessive, though it is *technically* required if you want to keep OP's method signature. — shmosel, May 31 '16 at 22:54
Interesting Answer; I would not have thought of computing numbers first. — PandaTank, May 31 '16 at 23:35

Java Find All Possible Combinations From Columns

2 Answers2