Generate all permutations of several 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 ith list has k_i elements. And now, I want to generate all n-elements list, where ith 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 shoulbe be equal to k_1*k_2*...k_n. Could you describe pseudo-code of this algorithm or use Java code? I can do this using nested for-loops when number of lists is hardcoded, but I'm completely blocked when n is customizable at runtime.

Answer 1

As you have already found out yourself, the usual trick is to think of the lists a non-uniform version of the g-adic numbers and do carry increment on the list index positions:

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

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

The trick is now as follows:

• start with index_pos = [0, 0, ...]
• increment index_pos[0].
  • If the result is larger or equal to lists[0].size(), set index_pos[0] = 0 and increment index_pos[1].
  • if index_pos[1] is larger than or equal to lists[1].size() ... and so on
• You are done when index_pos[n - 1] overflows

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