在Java中生成几个列表的所有排列 [英] Generate all permutations of several lists in Java

问题描述

我有n个列表，例如:

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

其中第i个列表具有k_i个元素. 现在，我想生成所有n元素列表，其中第i个元素来自L_i，我的意思是:

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]
...

列表总数应等于k_1*k_2*...k_n.您能描述这种算法的伪代码还是使用Java代码?当列表数量被硬编码时，我可以使用嵌套的for循环来做到这一点，但是当n在运行时可自定义时，我将完全被阻止.

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.

推荐答案

您已经发现自己了，通常技巧是将列表视为g-的非统一版本索引号并在列表索引位置进行进位增量:

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:

拥有n列表时，这些列表中具有n索引位置:

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

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

现在的诀窍如下:

• 以index_pos = [0, 0, ...]
开头
• 增加index_pos[0].
  • 如果结果大于或等于lists[0].size()，则设置index_pos[0] = 0并增加index_pos[1].
  • 如果index_pos[1]大于或等于lists[1].size() ...依此类推
  • 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

    Java中的非递归解决方案就像

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

    用法示例:

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

    这篇关于在Java中生成几个列表的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！