我最近在一次練習面試測驗中遇到了這個問題（如下所述），但它仍然讓我感到難過：
給定一個二維陣列 A，從中生成一個按行排列的一維陣列排列串列。
A = [
[1],
[5, 2],
[6]
]
Answer: [[1, 5, 2, 6], [1, 6, 5, 2], [5, 2, 1, 6], [5, 2, 6, 1], [6, 1, 5, 2], [6, 5, 2, 1]]
答案解釋：我們正在對行進行排列，所以這就像為 [a,b,c] 生成排列，其中每個元素都是可能變化長度的一維陣列。
我確信該解決方案涉及回溯，但每當我嘗試實施它時，我最終都會得到 5 個引數。我希望你們中的一個人能提供一個優雅的解決方案、偽代碼或解釋。
uj5u.com熱心網友回復：
您實際上只是在排列行順序，然后為每個排列展平矩陣。Python 示例：
from itertools import chain, permutations
def flatten(matrix):
return list(chain(*matrix))
def permute(matrix):
return [flatten(perm) for perm in permutations(matrix)]
用你的例子：
>>> M = [[1], [5, 2], [6]]
>>> permute(M)
[[1, 5, 2, 6], [1, 6, 5, 2], [5, 2, 1, 6], [5, 2, 6, 1], [6, 1, 5, 2], [6, 5, 2, 1]]
在另一種語言中，您可能必須實作自己的輔助函式來遍歷排列（可能使用遞回）和串列展平。
uj5u.com熱心網友回復：
在 Java 中，您可以這樣做（首先獲取所有索引的排列，然后使用它來生成 ans）：
public class RowWisePermutation {
public static void main(String[] args) {
int[][] A = {
{1},
{5, 2},
{6}
};
generateRowWisePermutation(A);
}
public static List<List<Integer>> generateRowWisePermutation(int[][] matrix) {
List<Integer> temp = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
List<List<Integer>> indexPermutation = new ArrayList<>();
int[] indexArr = new int[matrix.length];
for(int i = 0; i < matrix.length; i ) {
indexArr[i] = i;
}
backtrack(indexArr, temp, indexPermutation);
System.out.println(indexPermutation);
for(int i = 0; i < indexPermutation.size(); i ) {
List<Integer> row = new ArrayList<>();
List<Integer> indices = indexPermutation.get(i);
for(Integer index : indices) {
for(int j = 0; j < matrix[index].length; j ) {
row.add(matrix[index][j]);
}
}
ans.add(row);
}
System.out.println(ans);
return ans;
}
private static void backtrack(int[] arr, List<Integer> temp,
List<List<Integer>> indexPermutation) {
if(temp.size() == arr.length) {
indexPermutation.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < arr.length; i ) {
if(temp.contains(i)) { continue; }
temp.add(arr[i]);
backtrack(arr, temp, indexPermutation);
temp.remove(temp.size() - 1);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/420353.html
標籤：
上一篇：嵌入式系統，如何定義或計算時間段
下一篇：將根元素添加到回應模型