Most efficient way of combining elements of lists of items into sets of combinations?

Question

Let's say we're giving a List of lists of some items, say Strings.

list 1: "a", "b", "c"

list 2: "d", "e", "f"

list 3: "1", "2", "3"


results: (a, d, 1), (a, d, 2), ... (c, f, 3)

(the real use case has nothing to do with strings and such, this is just a mock up)

I wrote a recursive method to do it, but I am not happy with it because it creates a lot of temporary sets that get tossed (yeah, I know object creation is cheap in java, usually fewer cpu instructions than a malloc in C (source: Java Concurrency in Action, p241), eden GC is cheap, blah blah blah. humor me :).

void combine(List<List<String>> itemLists, List<Set<String>> combinations, Set<String> partial) {
    if (itemLists == null || itemLists.isEmpty()) return;
    List<String> items = itemLists.get(0);
    for (String s : items) {
        Set<String> tmpSet = new HashSet<>(partial);
        tmpSet.add(s);
        if (itemLists.size() == 0) //termination test
            combinations.add(tmpSet);
        else
            combine(itemLists.subList(1, itemLists.size()), combinations, tmpSet);
    }
}

So, how would you go about this?

edit: To be clear, I do not want to create permutations. I want to create sets that are sizeof(list of lists) big.

Well, you can just do it in a loop ... (no need for recursion). — Greg Kopff, May 09 '12 at 00:36
Do you want to keep all the sets in memory? Or are you searching for a particular combination or property in the resulting sets? — Erica, May 09 '12 at 00:42
@Paul Vargas - This is not what I want. See my edit and look at my code. — marathon, May 09 '12 at 00:48
[Here is a short answer](http://stackoverflow.com/a/5024299/312172), [here a longer one with Iterator and Iterable](http://stackoverflow.com/a/10084048/312172). The keyword is 'cartesian product' and what is the most efficient one? In terms of size, I guess, since you talk about GC? Or speed? — user unknown, May 09 '12 at 01:15

score 3 · Answer 1 · answered May 10 '12 at 14:45

What you're looking for is the "cartesian product."

If you're okay with using Sets instead of Lists, you can use Sets.cartesianProduct. There is still some garbage allocated as you iterate over the resulting Lists... but not nearly as much as other approaches.

(Note that as a common library method, it's been very exhaustively tested, so you can have a little more confidence in it than in pasting dozens of lines of code out of SO.)

FYI there has been a request for Lists.cartesianProduct as well, but I don't think anyone's working on it.

Erica · Accepted Answer · 2012-05-09T02:08:59.917

You want a list of all possible sets, containing exactly one value from each of the provided lists, assuming that the number of lists is variable and the size of those lists is also variable. Correct?

Something like this, then?

static List<Set<String>> combine(List<List<String>> itemLists)
{
    // Calculate how many combinations we'll need to build
    int remainingCombinations = itemLists.get(0).size();
    for(int i=1; i<itemLists.size(); i++)
    {
        remainingCombinations *= itemLists.get(i).size();
    }

    List<Set<String>> allSets = new ArrayList<Set<String>>();

    // Generate this combination
    for (;remainingCombinations > 0; remainingCombinations --)
    {
        Set<String> currentSet = new HashSet<String>();
        int positionInRow = remainingCombinations;

        // Pick the required element from each list, and add it to the set.
        for(int i=0; i<itemLists.size(); i++)
        {
            int sizeOfRow = itemLists.get(i).size();
            currentSet.add(itemLists.get(i).get(positionInRow % sizeOfRow));
            positionInRow /= sizeOfRow;
        }

        allSets.add(currentSet);
    }
    return allSets;
}

score 1 · Answer 3 · answered May 09 '12 at 01:14

This is more efficient: Approach it the same way counting works (each "position" is one of your lists and each "digit" that can go in that position is an element of your list):

List<Set<String>> combine( List<List<String>> input ){

    final int n = input.size();
    int[] index = new int[n];

    List<Set<Sting>> result = new List<>();

    int position = 0;
    while( position < n ){ // "overflow" check

        // Add set to result.
        Set<String> set = new HashSet<>();
        for( int i=0; i<n; i++ )
            set.add( input.get(i).get( index[i] ) );
        result.add( set );

        // Now the "hard" part: increment the index array
        position = 0;
        while( position < n ){

            if( index[ position ] < input.get( position ).size() ){
                index[position]++;
                break;
            }
            else // carry
                index[ position++ ] = 0;
        }
    }
    return result;
}

(Not tested, might have some bugs, but the main idea is there). In general, recursion is slower than iteration.

Most efficient way of combining elements of lists of items into sets of combinations?

3 Answers3