Find all permutations(cartesian product) from a list> in java

Question

If I have n lists:

List<int> list1 = new List<int>
List<int> list2 = new List<int>
...
List<int> listn = new List<int>

each of them contains different number of elements,e.g.

list1.add(1)
list1.add(2)
list2.add(3)
list2.add(4)
list2.add(5)
list3.add(6)
...
listn.add(100000)
listn.add(100001)

and one list of lists

List<List<int>> biglist = new ArrayList<List<int>>
biglist.add(list1)
biglist.add(list2)
...
biglist.add(listn)

then how can I generate permuationList from the biglist that contains elements, suppose the listn has m elements:

[biglist.get(1).get(1),biglist.get(2).get(1), ..., biglist.get(n-1).get(1), biglist.get(n).get(1)]
[biglist.get(1).get(1),biglist.get(2).get(1), ..., biglist.get(n-1).get(1), biglist.get(n).get(2)]
...
[biglist.get(1).get(1),biglist.get(2).get(1), ..., biglist.get(n-1).get(1), biglist.get(n).get(m)]
[biglist.get(1).get(1),biglist.get(2).get(1), ..., biglist.get(n-1).get(2), biglist.get(n).get(1)]
....

Thanks!

possible duplicate of [permutations and combinations of Arraylists in Java?](http://stackoverflow.com/questions/11485497/permutations-and-combinations-of-arraylists-in-java) — , Nov 18 '14 at 06:38
https://code.google.com/p/combinatoricslib/#3._Simple_combinations maybe — , Nov 18 '14 at 12:30
@RC. it seems that there is only one list, and my case is n list, every list has different number of elements, say 3 list, with 3,4,5 number of elements, then the final result I want is 3*4*5=60 lists, every list with 3 elements. Thanks! — user, Nov 18 '14 at 12:37
@user, check my updated answer, I think that is what you want. — JaskeyLam, Nov 19 '14 at 07:25
@Ted Hopp, thanks for your answer, but personally, the Jaskey's one is clear for me, thanks! — user, Nov 20 '14 at 05:28

score 0 · Answer 1 · edited Nov 18 '14 at 08:31

There are many solutions to solve above problems. This is one of them. Please have a look.

public static void main(String args[]) throws Exception {
    List<Integer> list1 = new ArrayList<Integer>();
    List<Integer> list2 = new ArrayList<Integer>();
    list1.add(1);
    list1.add(2);
    list2.add(3);
    list2.add(4);
    List<List<Integer>> biglist = new ArrayList<List<Integer>>();
    biglist.add(list1);
    biglist.add(list2);
    print(biglist);
}

private static void print(List<List<Integer>> biglist) {
    List<Integer> list1 = biglist.get(0);
    List<Integer> list2 = biglist.get(1);
    for (Integer i : list1) {
        printCombination(i, list2);
    }
}

private static void printCombination(Integer i, List<Integer> list2) {
    for (Integer j : list2) {
        System.out.println("[" + i + ", " + j + "]");
    }
}

Thanks

it seems that it doesn't work for unknown number of list. The questions' lists are examples. What I have now are list0,list1,...listn, (the number of list can get by biglist.size() )and for each list, there are different number of elements, say, list0 has 5 elements(get by biglist.get(0).size), list1 has 6 element. Thanks! — user, Nov 18 '14 at 06:55

JaskeyLam · Accepted Answer · 2014-11-19T07:26:31.990

You can use recursion to achieve this, to merge the first list with the tail list(a list of list).

public class Permutation   {
    public static List<List<Integer>> calculate(List<List<Integer>> input) {
        List<List<Integer>> result= new ArrayList<List<Integer>>();//

        if (input.isEmpty()) {  // If input is an empty list
            result.add(new ArrayList<Integer>());// then add empty list to the resultand return
            return result;
        } else {//here we have a non-empty list to process
            List<Integer> head = input.get(0);//get the first list as a head
            List<List<Integer>> tail= calculate(input.subList(1, input.size()));//recursion to calculate a tail list to calculate a tail list
            for (Integer h : head) {//we merge every head element with every tail list
                for (List<Integer> t : tail) {
                    List<Integer> resultElement= new ArrayList<Integer>();//here is a new element of our result list
                    resultElement.add(h);//firstly, add the head element to this tmp list
                    resultElement.addAll(t);//add all the element from the tail list
                    result.add(resultElement);
                }
            }
        }
        return result;
    }


    public static void main(String[] args) {
        List<List<Integer>> bigList=Arrays.asList(Arrays.asList(1,2),Arrays.asList(3,4),Arrays.asList(5,6));
        System.out.println(calculate(bigList));
    }
}

output:

   [[1, 3, 5, 7], [1, 3, 5, 8], [1, 3, 6, 7], [1, 3, 6, 8], [1, 4, 5, 7], [1, 4, 5, 8], [1, 4, 6, 7], [1, 4, 6, 8], [2, 3, 5, 7], [2, 3, 5, 8], [2, 3, 6, 7], [2, 3, 6, 8], [2, 4, 5, 7], [2, 4, 5, 8], [2, 4, 6, 7], [2, 4, 6, 8]]

sorry for the confusion, I have n lists (list1, list2, ..., listn, rather than 2), each of them contains different number of elements — user, Nov 18 '14 at 11:03
@user, if you have three list, [1,2][3,4],[5,6]. You need [1,3][1,4][1,5][1,6],[2,3][2,4],[2,5],[2,6],[3,5][3,6][4,5][4,6]? — JaskeyLam, Nov 18 '14 at 11:06

score 0 · Answer 3 · edited May 23 '17 at 12:12

Here's a general approach to generate all combinations of elements from a list of lists:

public static List<List<Integer>> generateCombinations(List<List<Integer>> lists) {
    final List<List<Integer>> result = new ArrayList<List<Integer>>();
    final List<Integer> accumulator = new ArrayList<Integer>();
    generateCombos(lists, result, accumulator, 0);
    return result;
}

// recursive helper method
private static void generateCombos(
        List<List<Integer>> input,
        List<List<Integer>> result,
        List<Integer> accumulator,
        int i)
{
    if (i < input.size()) {
        // add each element of the current list to the accumulator
        // and recurse with the next element of the input
        for (Integer elt : input.get(i)) {
            accumulator.add(i, elt);
            generateCombos(input, result, accumulator, i + 1);
            accumulator.remove(i);
        }
    } else {
        // add what's in the accumulator (as a new list, so we can reuse accumulator)
        result.add(new ArrayList<Integer>(accumulator));
    }
}

Note that this generates all combinations of elements—one element from each list. From your example, I think that this is what you are after. If you actually want all permutations, you could start with this and then generate all reorderings of each element of the result (using, say, the approach presented in this thread).

Find all permutations(cartesian product) from a list> in java

3 Answers3