Generating all possible combinations from list of sublists:

[blackrobe]

Hey all,

I've been struggling for the past few days with a "recursive" function that was driving me crazy till this moment.

So, the function takes a list of sublists, each sublist containing a number of strings. Then, the function returns a list of lists of all possible combinations that could be generated from this list.

so for example:
the list of lists could be: [["1a", "1b", "1c"], ["2a", "2b"], ["3a", "3d"]]
the result would be:
["1a", "2a", "3a"]
["1a", "2a", "3d"]
["1a", "2b", "3a"]
["1a", "2b", "3d"]
["1b", "2a", "3a"]
["1b", "2a", "3d"]
["1b", "2b", "3a"]
["1b", "2b", "3d"]
["1c", "2a", "3a"]
["1c", "2a", "3d"]
["1c", "2b", "3a"]
["1c", "2b", "3d"]

If any of you has a working strategy to solve this problem, I would be grateful. Thank you.

[VernonDozier]

The first list has 3 elements, the second has 2 elements, the third has 2 elements, so there are 3 x 2 x 2 = 12 possibilities. Use a triple nested loop:

for (int i = 0; i < 3; i++)
{
  for (int j = 0; j < 2; j++)
  {
    for (int k = 0; k < 2; k++)
    {
       // add an element to the list of lists.
    }
  }
}

[javaAddict]

That is correct assuming that the number of the lists will be fixed as well as their length.
A more dynamic approach will be a little more complicated:
Calculate first the number of possible combinations by getting their length and then have 1 for loop:

for (int i=0;i<12 /*number of combinations*/ ;i++) {

}

Inside you will have code that generates ONE possible combination. Maybe you could use a while loop in order to get each element from each list by increasing an index (row, or col) and by checking if they have reached the length of each sublist

[blackrobe]

I need the more dynamic approach...Neither the number of lists nor the their length will be fixed..the number of possible combinations could be anything...and if I got to find the number of combinations I will have to loop through each sublist, which is not my intention since I'm trying to do it the recursive way.

My strategy for approaching this was removing the first sublist, getting a list of all the possible choices for the remaining lists, and then adding each element from the first sublist on a copy of each of those results, recursively.

But there seem to be something wrong with my logic...any help??

[brennerd]

I needed the same functionality, it took me some time, but the following code seems to work. The Integers can easily be replaced with whatever you want.

// i is used for recursion, for the initial call this should be 0
private List<List<Integer>> test2(List<List<Integer>> input, int i) {
	
	// stop condition
	if(i == input.size()) {
		// return a list with an empty list
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		result.add(new ArrayList<Integer>());
		return result;
	}
	
	List<List<Integer>> result = new ArrayList<List<Integer>>();
	List<List<Integer>> recursive = test2(input, i+1); // recursive call
	
	// for each element of the first list of input
	for(int j = 0; j < input.get(i).size(); j++) {
		// add the element to all combinations obtained for the rest of the lists
		for(int k = 0; k < recursive.size(); k++) {
                        // copy a combination from recursive
			List<Integer> newList = new ArrayList<Integer>();
			for(Integer integer : recursive.get(k)) {
				newList.add(integer);
			}
			// add element of the first list
			newList.add(input.get(i).get(j));
                        // add new combination to result
			result.add(newList);
		}
	}
	return result;
}

[boehr]

Hi,

I know this is an old thread, but anyway I had the same problem and i think i solved it. The method allows to generate one combination at a time. This means you do not have to create all possible combinations and store them in your ram. You can just get the next combination of elements when you need it.

How does it work?
Ok think of the following.
If we write the number 456 then it means 4*10² + 4*10¹ + 6*10⁰ .
So the basis of our numbersystem is 10. When we add 1 to lets say 18 we just increment the 8 to 9. But if we add 1 to 19 we can not go on like this because we have no more arabic numerals. So we get an overflow and set the 9 back to one.
We remember the overflow and add it to the next arabic numeral and thus get 20.

The code provided below is based on this system. However the base of each arabic numeral is diffrent. It is the amount of elements in a sublist.
This allows to just add 1 to this "number" and to retrive the next element.
The arabic numerals are then used as indexes of the sublists.

I added a little example main to the code so you can see how it can be used.
Please let me know if you like it :-)
The code sarts here:

package de.unikl.informatik.boehr.Algorithm.util;

import de.unikl.informatik.boehr.DTP.model.DTPPhase;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Frank Böhr
 */
public class ListCombinationGenerator<T> {


    //The list from which the combinations should be enerated
    private List<List<T>> uncombinedList;

    //A list representig the current combination
    private List<Pair> currentCombination = new LinkedList<Pair>();

    //telling if there are more combinations
    private boolean hasMoreCombinations = true;


//Create the object and set up the needed informations
public ListCombinationGenerator(List<List<T>> uncombinedList) {
    this.uncombinedList = uncombinedList;

    //Set up the managment information
    Iterator<List<T>> iter = this.uncombinedList.iterator();
    while(iter.hasNext()){
        List<T> currentSubList = iter.next();
        Pair p = new Pair(1,currentSubList.size());
        currentCombination.add(p);

    }
    
}



//This method does not work recursivly.
//It generates a singel combination at each time it is called.
//This means it is not needed to keep all combinations in the RAM.
public List<T> getNextCombination(){

    
    //remember the current combination and return it later as the result
    //the next combination is generated in the following to see if there are realy more combinations

    //contains the result of this method call
    List<T> result = new LinkedList<T>();
    Iterator<Pair> currentCombinationIterator = this.getCurrentCombination().iterator();
    Iterator<List<T>> uncombinedListIterator = this.getUncombinedList().iterator();

    //fill the result variable according to the current values in currentcombination
    while(currentCombinationIterator.hasNext() && uncombinedListIterator.hasNext()){
        Pair currentPair = currentCombinationIterator.next();
        List<T> currentSublist = uncombinedListIterator.next();
        result.add(currentSublist.get(currentPair.getCurrentValue()-1));

    }


    //In the first step the value which gets added to the number.
    //During the algorithem it gets the current overflow
    int overflow = 1;

    //Go from left to right and behave as if the numbers in the
    //currentCombinationList represent a number. This number
    //has a diffrent base at each position. This base is the
    //max count of the pair. The next combination is obtaind by
    //adding 1 to this number.
    Iterator<Pair> iter = this.getCurrentCombination().iterator();
    while(iter.hasNext()){
        //The current position in the number
        Pair currentPair = iter.next();
       
        
        //check if we get a further overflow by adding the
        //overflow from the previous step or if we are done
        //if there is an overflow reset the current number
        //and remember teh new overflow
       
            //if we have an further overflow
            if((currentPair.getCurrentValue()+overflow)>currentPair.getMaxValue()){
                //calculate the new overflow
                overflow = (currentPair.getCurrentValue()+overflow) - currentPair.getMaxValue();
                //reset the current value
                currentPair.setCurrentValue(1);
                
            }else{
                //if we do net have an further overflow
                currentPair.setCurrentValue(currentPair.getCurrentValue()+1);
                //This is indicating that there is one more element
                overflow=0;
                break;

            }

    }


    //remember if there are more combinations
    if(overflow!=0){
        this.setHasMoreCombinations(false);
    }

    //System.out.println(result+ " hasMoreCombinations: " + this.hasMoreCombinations());
    
    return result;
}



public static void main(String[] args){

        //Set up some lists
        List<String> l1 = new ArrayList<String>();
        l1.add(new String("1"));
        l1.add(new String("2"));

        List<String> l2 = new ArrayList<String>();
        l2.add(new String("1"));
      
        
        List<String> l3 = new ArrayList<String>();
        l3.add(new String("1"));
        l3.add(new String("2"));
        l3.add(new String("3"));


        List<String> l4 = new ArrayList<String>();
        l4.add(new String("1"));
        l4.add(new String("2"));
        l4.add(new String("3"));
        l4.add(new String("4"));

        List<String> l5 = new ArrayList<String>();
        l5.add(new String("1"));
        l5.add(new String("2"));

        List<String> l6 = new ArrayList<String>();
        l6.add(new String("1"));
        l6.add(new String("2"));

        List<String> l7 = new ArrayList<String>();
        l7.add(new String("1"));
        l7.add(new String("2"));

        List<String> l8 = new ArrayList<String>();
        l8.add(new String("1"));
        l8.add(new String("2"));

        List<String> l9 = new ArrayList<String>();
        l9.add(new String("1"));
        l9.add(new String("2"));


        List<List<String>> ll = new ArrayList<List<String>>();
        
        ll.add(l1);
        ll.add(l2);
        ll.add(l3);
        ll.add(l4);
        ll.add(l5);
        ll.add(l6);
        ll.add(l7);
        ll.add(l8);
        ll.add(l9);
        

        ListCombinationGenerator<DTPPhase> lcg = new ListCombinationGenerator(ll);
            long before = System.nanoTime();
        while(lcg.hasMoreCombinations()){  
          List<DTPPhase> currentTupel = lcg.getNextCombination();
          System.out.println("currentTupel: " + currentTupel+ "hasMoreCombinations: "  + lcg.hasMoreCombinations);
        }
            long after = System.nanoTime();
            System.out.println("Nanosconds: " + (after-before) );
}

    private List<Pair> getCurrentCombination() {
        return currentCombination;
    }

    private void setCurrentCombination(List<Pair> currentCombination) {
        this.currentCombination = currentCombination;
    }

    public boolean hasMoreCombinations() {
        return hasMoreCombinations;
    }

    public void setHasMoreCombinations(boolean hasMoreCombinations) {
        this.hasMoreCombinations = hasMoreCombinations;
    }

    public List<List<T>> getUncombinedList() {
        return uncombinedList;
    }

    public void setUncombinedList(List<List<T>> uncombinedList) {
        this.uncombinedList = uncombinedList;
    }


    private class Pair{

        int currentValue = 1;
        int maxValue = 1;

        public Pair(int currentValue, int maxValue){
            this.currentValue = currentValue;
            this.maxValue=maxValue;
        }

        public int getCurrentValue() {
            return currentValue;
        }

        public void setCurrentValue(int currentValue) {
            this.currentValue = currentValue;
        }

        public int getMaxValue() {
            return maxValue;
        }

        public void setMaxValue(int maxValue) {
            this.maxValue = maxValue;
        }

        @Override
        public String toString(){
            return "(CurrentVal: " + this.getCurrentValue() + " MaxVal: " + this.getMaxValue()+")";


        }

    }


}

The output looks like this:
currentTupel: [1, 1, 1, 1, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 1, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 1, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 1, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 1, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 1, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 2, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 2, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 2, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 2, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 2, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 2, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 3, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 3, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 3, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 3, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 3, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 3, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 4, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 4, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 4, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 4, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 4, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 4, 1, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 1, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 1, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 1, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 1, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 1, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 1, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 2, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 2, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 2, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 2, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 2, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 2, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 3, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 3, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 3, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 3, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 3, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 3, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 4, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 4, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 4, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 4, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 4, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 4, 2, 1, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 1, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 1, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 1, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 1, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 1, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 1, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 2, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 2, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 2, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 2, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 2, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 2, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 3, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 3, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 3, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 3, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 3, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 3, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 4, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 4, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 4, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 4, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 4, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 4, 1, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 1, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 1, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 1, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 1, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 1, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 1, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 2, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 2, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 2, 2, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 2, 2, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 3, 2, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 3, 2, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [1, 1, 1, 3, 2, 2, 1, 1, 1]hasMoreCombinations: true
currentTupel: [2, 1, 1, 3, 2, 2, 1, 1, 1]hasMoreCombinations: true
and so on ....

have fun :-)

[boehr]

sorry replace DTPPhase with String :-)

[sebastien76]

Studying same problem, write my own implementation.

Sebastien Boutte

public static <T> int combinations(List<List<T>> list) {
		int count = 1;
		for(List<T> current : list) {
			count = count * current.size();
		}
		return count;
	}

        public static <T> List<List<T>> combinate(List<List<T>> uncombinedList) {
		List<List<T>> list = new ArrayList<List<T>>();
		int index[] = new int[uncombinedList.size()];
		int combinations = combinations(uncombinedList)-1;
		// Initialize index
		for(int i = 0; i< index.length; i++) {
			index[i] = 0;
		}
		// First combination is always valid
		List<T> combination = new ArrayList<T>();
		for(int m = 0; m< index.length; m++) {
			combination.add(uncombinedList.get(m).get(index[m]));
		}
		list.add(combination);
		for(int k = 0; k< combinations; k++) {
			combination = new ArrayList<T>();
			boolean found = false;
			// We Use reverse order
			for(int l = index.length-1 ; l >=0 && found == false; l--) {
				int currentListSize = uncombinedList.get(l).size();
				if (index[l] < currentListSize-1) {
					index[l] = index[l]+1;
					found = true;
				}
				else {
					// Overflow
					index[l] = 0;
				}
			}
			for(int m = 0; m< index.length; m++) {
				combination.add(uncombinedList.get(m).get(index[m]));
			}
			list.add(combination);
		}
		return list;
	}

[ashwinimoily]

I have the same issue. But I need to have 3 numbers at a time from each list. For example, the list contains
[1,2,3,4,5,6]
[2,4,5]
[6,7,8]
[4,5,7,8,9,2]
Then the result should be:
[1,2,3][2,4,5][6,7,8][4,5,7]
[1,2,3][2,4,5][6,7,8][8,9,2]
[4,5,6][2,4,5][6,7,8][4,5,7]
[4,5,6][2,4,5][6,7,8][8,9,2]

Could someone help me write an efficient recursive program for this?
Thank you.

[Mavericks]

sorry replace DTPPhase with String :-)

I get the DTP.Model doesn't exist even after the replacemnt with String

[Mavericks]

Studying same problem, write my own implementation.

Sebastien Boutte

public static <T> int combinations(List<List<T>> list) {
		int count = 1;
		for(List<T> current : list) {
			count = count * current.size();
		}
		return count;
	}

        public static <T> List<List<T>> combinate(List<List<T>> uncombinedList) {
		List<List<T>> list = new ArrayList<List<T>>();
		int index[] = new int[uncombinedList.size()];
		int combinations = combinations(uncombinedList)-1;
		// Initialize index
		for(int i = 0; i< index.length; i++) {
			index[i] = 0;
		}
		// First combination is always valid
		List<T> combination = new ArrayList<T>();
		for(int m = 0; m< index.length; m++) {
			combination.add(uncombinedList.get(m).get(index[m]));
		}
		list.add(combination);
		for(int k = 0; k< combinations; k++) {
			combination = new ArrayList<T>();
			boolean found = false;
			// We Use reverse order
			for(int l = index.length-1 ; l >=0 && found == false; l--) {
				int currentListSize = uncombinedList.get(l).size();
				if (index[l] < currentListSize-1) {
					index[l] = index[l]+1;
					found = true;
				}
				else {
					// Overflow
					index[l] = 0;
				}
			}
			for(int m = 0; m< index.length; m++) {
				combination.add(uncombinedList.get(m).get(index[m]));
			}
			list.add(combination);
		}
		return list;
	}

What is the demo code to run this program? Are there any special conditions where this program works and won't work?