我試圖在集合集合中找到排列，條件是每個內部集合中的元素只能出現一次。例如，我有一個列表列表：[[a，b]，[c，d]，[e，f]]，我的結果將是這樣的：[a][c][e]...[a,c] ('a' appeared and excluded 'b')[b,d][c,e]...[a, c, e][b, d, f][a, c, f]and so on...或者至少幫我一些答案的鏈接 - 我是一個乞丐，仍然不知道使用搜索引擎提問所需的正確短語。
1 回答
HUX布斯
TA貢獻1876條經驗 獲得超6個贊
具有未排序輸出的遞歸解決方案：
public static <T> List<List<T>> permutations(List<List<T>> lists) {
return permutations(lists, new ArrayList<>());
}
private static <T> List<List<T>> permutations(List<List<T>> lists, List<T> prefix) {
if (lists.isEmpty()) return Arrays.asList(prefix);
List<T> head = lists.get(0);
List<List<T>> tail = lists.subList(1, lists.size());
List<List<T>> result = new ArrayList<>();
for (T t : head) {
List<T> p = new ArrayList<>(prefix);
p.add(t);
result.addAll(permutations(tail, p));
}
result.addAll(permutations(tail, prefix));
return result;
}
對于示例列表，輸出為：[[a,b],[c,d],[e,f]]
[[a, c, e], [a, c, f], [a, c], [a, d, e], [a, d, f], [a, d], [a, e], [a, f], [a],
[b, c, e], [b, c, f], [b, c], [b, d, e], [b, d, f], [b, d], [b, e], [b, f], [b],
[c, e], [c, f], [c], [d, e], [d, f], [d], [e], [f], []]
如果您需要按大小排序，則此速度大約慢2-3倍：
public static <T> List<List<T>> permutations(List<List<T>> lists) {
List<List<T>> result = new ArrayList<>();
for (int i = 0; i <= lists.size(); i++) {
result.addAll(permutations(lists, i));
}
return result;
}
private static <T> List<List<T>> permutations(List<List<T>> lists, int count) {
if (count == 0) return Arrays.asList(new ArrayList<>());
List<List<T>> result = new ArrayList<>();
for (int i = 0; i < lists.size() - count + 1; i++) {
for (T t : lists.get(i)) {
for (List<T> r : permutations(lists.subList(i + 1, lists.size()), count - 1)) {
r = new ArrayList<>(r);
r.add(0, t);
result.add(r);
}
}
}
return result;
}
輸出：
[[], [a], [b], [c], [d], [e], [f], [a, c], [a, d], [a, e], [a, f],
[b, c], [b, d], [b, e], [b, f], [c, e], [c, f], [d, e], [d, f],
[a, c, e], [a, c, f], [a, d, e], [a, d, f], [b, c, e], [b, c, f], [b, d, e], [b, d, f]]
添加回答
舉報
0/150
提交
取消