algorithm - 有没有一种算法可以从二维列表中找到没有重复的排列？

Question

我的输入由整数值的二维列表组成。二维列表可以包含三个列表，如下例所示：

L1   L2    L3
--------------
1    11    111
2    22    222
3    33
4

目标是以正确的顺序将每个元素与其他元素组合在一起。结果也必须是一个二维列表。二维列表中的每个列表的大小为 n，其中 n 是输入列表的数量。将生成以下结果：

L1:  1, 11, 111
L2:  1, 11, 222
L3:  1, 22, 111
L4:  1, 22, 222
L5:  1, 33, 111
L6:  1, 33, 222

L7:  2, 11, 111
L8:  2, 11, 222
L9:  2, 22, 111
.
.
.
L24: 4, 33, 222

一切都必须有正确的顺序，如示例所示。

标签： algorithmrecursioniterationtime-complexity

Answer 1

这个问题可以递归解决。该算法非常简单，唯一棘手的部分是当列表具有重复数字时避免重复排列。这样做的一个好方法是对每个列表进行排序，因此在从每个列表中选择整数时，很容易判断是否选择了特定数字。以下是以您提供的示例作为测试用例的实现。您可以更改列表的值以包含重复的数字，并查看输出不包含重复的排列。

public class ListPermutation {
    public static List<List<Integer>> generateUniqueListPermutations(List<List<Integer>> lists) {
        List<List<Integer>> permutations = new ArrayList<>();
        if(lists == null || lists.size() == 0) {
            return permutations;
        }
        //sort each input list
        for(List<Integer> list : lists) {
            Collections.sort(list);
        }
        permutationHelper(lists, permutations, new ArrayList<>(), 0);
        return permutations;
    }
    private static void permutationHelper(List<List<Integer>> lists, List<List<Integer>> permutations, List<Integer> list, int idx) {
        if(idx == lists.size()) {
            permutations.add(new ArrayList<>(list));
            return;
        }
        List<Integer> currList = lists.get(idx);
        for(int i = 0; i < currList.size(); i++) {
            if(i > 0 && currList.get(i) == currList.get(i - 1)) {
                continue;
            }
            list.add(currList.get(i));
            permutationHelper(lists, permutations, list, idx + 1);
            list.remove(list.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>(); list1.add(1); list1.add(2); list1.add(3); list1.add(4);
        List<Integer> list2 = new ArrayList<>(); list2.add(11); list2.add(22); list2.add(33);
        List<Integer> list3 = new ArrayList<>(); list3.add(111); list3.add(222);
        List<List<Integer>> lists = new ArrayList<>(); lists.add(list1); lists.add(list2); lists.add(list3);
        generateUniqueListPermutations(lists);
    }
}