Generate all permutations of multiple lists in Java

Question

I have n lists, for example:

 L_1 = [a_11, a_12, ...] L_2 = [a_21, a_22, ...] ... L_n = [a_n1, a_n2, ...] 

where i th list has k_i elements. And now I want to generate the whole list of n -elements, where the i th element is from L_i , I mean:

 [a_11, a_21, ..., a_n1] [a_11, a_21, ..., a_n2] ... [a_11, a_22, ..., a_n1] [a_11, a_22, ..., a_n2] ... [a_12, a_21, ..., a_n1] [a_12, a_21, ..., a_n2] ... [a_12, a_22, ..., a_n1] [a_12, a_22, ..., a_n2] ... 

The total number of lists should be equal to k_1*k_2*...k_n . Could you describe the pseudo-code of this algorithm or use Java code? I can do this with nested for-loops when the number of lists is hard-coded, but I'm completely blocked when n configured at runtime.

Answer 1

As you already found out, the usual trick is to think about lists of an uneven version of g-adic numbers and carry an increment in the list index positions:

When you have lists n , you have n index positions in these lists:

 index_pos = [i0, ..., in-1] 

Now the trick is as follows:

• start with index_pos = [0, 0, ...]
• increment index_pos[0] .
  • If the result is greater than or equal to lists[0].size() , set index_pos[0] = 0 and increase index_pos[1] .
  • if index_pos[1] greater than or equal to lists[1].size() ... etc.
• index_pos[n - 1] when index_pos[n - 1] overflows

A non-recursive solution in Java would be like

 public static <T> void permute( final List<List<T>> lists, final Consumer<List<T>> consumer ) { final int[] index_pos = new int[lists.size()]; final int last_index = lists.size() - 1; final List<T> permuted = new ArrayList<T>(lists.size()); for (int i = 0; i < lists.size(); ++i) { permuted.add(null); } while (index_pos[last_index] < lists.get(last_index).size()) { for (int i = 0; i < lists.size(); ++i) { permuted.set(i, lists.get(i).get(index_pos[i])); } consumer.accept(permuted); for (int i = 0; i < lists.size(); ++i) { ++index_pos[i]; if (index_pos[i] < lists.get(i).size()) { /* stop at first element without overflow */ break; } else if (i < last_index) { index_pos[i] = 0; } } } } 

Usage example:

 public static void main(String[] args) { final List<List<Integer>> lists = new ArrayList<List<Integer>>(); final List<Integer> list0 = new ArrayList<Integer>(); list0.add(0); list0.add(1); list0.add(2); list0.add(4); lists.add(list0); lists.add(list0); lists.add(list0); permute(lists, (permutation -> System.out.println(permutation))); } 

Answer 2

Ok, I implemented this algorithm.

 import com.google.common.collect.Lists; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class PermutationGenerator { private List<List<Integer>> result; private List<List<Integer>> data; public List<List<Integer>> permutate(List<List<Integer>> data) { this.data = data; this.result = Lists.newArrayList(); List<Integer> integers = new ArrayList<Integer>(Collections.nCopies(data.size(), 0)); foo(0, data.size() - 1, integers); return result; } private void foo(Integer index, Integer maxIndex, List<Integer> output) { List<Integer> list = data.get(index); for (int i = 0; i < list.size(); i++) { output.set(index, list.get(i)); if (index == maxIndex) { result.add(Lists.newArrayList(output)); } else { foo(index + 1, maxIndex, output); } } } } 

Testing Class:

 import com.google.common.collect.Lists; import org.junit.Test; import java.util.Arrays; import java.util.List; public class PermutationGeneratorTest { @Test public void test() throws Exception { // given PermutationGenerator pg = new PermutationGenerator(); List<Integer> list1 = Lists.newArrayList(1, 2, 3); List<Integer> list2 = Lists.newArrayList(4, 5); List<Integer> list3 = Lists.newArrayList(6, 7, 8, 9); List<List<Integer>> input = Lists.newArrayList(list1, list2, list3); // when List<List<Integer>> output = pg.permutate(input); // then print(output); } private void print(List<List<Integer>> output) { for (List<Integer> list : output) { System.out.println(Arrays.toString(list.toArray())); } System.out.println("TOTAL: " + output.size()); } } 

Output:

 [1, 4, 6] [1, 4, 7] [1, 4, 8] [1, 4, 9] [1, 5, 6] [1, 5, 7] [1, 5, 8] [1, 5, 9] [2, 4, 6] [2, 4, 7] [2, 4, 8] [2, 4, 9] [2, 5, 6] [2, 5, 7] [2, 5, 8] [2, 5, 9] [3, 4, 6] [3, 4, 7] [3, 4, 8] [3, 4, 9] [3, 5, 6] [3, 5, 7] [3, 5, 8] [3, 5, 9] TOTAL: 24