我的输入包含一个二维整数值列表。 二维列表可以包含三个列表,如下例所示:
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
一切都必须像示例所示那样按正确的顺序排列。
最佳答案
这个问题可以递归求解。该算法非常简单,唯一棘手的部分是在列表具有重复数字时避免重复排列。这样做的一个好方法是对每个列表进行排序,因此当从每个列表中选取整数时,很容易判断是否已选取特定数字。以下是以您提供的示例作为测试用例的实现。您可以更改列表的值以包含重复的数字,并查看输出不包含重复的排列。
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);
}
}
关于algorithm - 是否有一种算法可以从二维列表中找到不重复的排列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55418865/