Java：數組的排列

Question

我對Java中的遞歸不太熟悉。我試圖編寫一個方法來計算整數數組的所有排列。我需要修改以下完美工作的方法，以便不用打印來篩選數組的所有排列，而是將它們插入到二維數組中。所以該方法的輸入是整數的n的數組，並且輸出是具有n的二維數組！行和n列。我需要修改的程序是這樣的：

public static void permute(int[] array, int k) 
{ 
    for(int i=k; i<array.length; i++) 
    { 
     int temp; 
     temp = array[i]; 
     array[i] = array[k]; 
     array[k] = temp; 
     permute(array, k+1); 
     int temp2; 
     temp2 = array[i]; 
     array[i] = array[k]; 
     array[k] = temp2; 
    } 
    if (k == array.length-1) 
    { 
     Array.printValues(array); 
    } 
} 

所以，我需要的是這樣的：

public static int[][] permute(int[] array, int k) 
{ 
    //code here 
} 

謝謝。

Answer 1

將它們粘在一個列表中，然後從中取出一個數組。您可以直接使用int [] []，但不知道第一個維度值，沒有額外的重複。

public static int[][] permuteToArray(int[] array, int k){ 
    ArrayList<int[]> arrL=new ArrayList<>(); 
    for(int i=k; i<array.length; i++) 
    { 
     int temp; 
     temp = array[i]; 
     array[i] = array[k]; 
     array[k] = temp; 
     permute(array, k+1, arrL); 
     int temp2; 
     temp2 = array[i]; 
     array[i] = array[k]; 
     array[k] = temp2; 
    } 
    if (k == array.length-1) 
    { 
     arrL.add(array); 
    } 
    return arrL.toArray(new int[][]); 
} 

變化permute(是：

public static void permute(int[] array, int k, ArrayList arrL) //raw type, I know 
{ 
    for(int i=k; i<array.length; i++) 
    { 
     int temp; 
     temp = array[i]; 
     array[i] = array[k]; 
     array[k] = temp; 
     permute(array, k+1); 
     int temp2; 
     temp2 = array[i]; 
     array[i] = array[k]; 
     array[k] = temp2; 
    } 
    if (k == array.length-1) 
    { 
     arrL.add(array); 
    } 
} 

Answer 2

public static void _permute(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, int k, boolean[] status, int[] array) 
{ 
    if (cur.size() == k) { 
    res.add((ArrayList<Integer>)cur.clone()); 
    return; 
    } 
    for (int i = 0; i < k; i++) 
    { 
    if (status[i]) continue; 
    cur.add(array[i]); 
    status[i] = true; 
    _permute(res, cur, k, status, array); 
    status[i] = false; 
    cur.remove(new Integer(array[i])); 
    } 
} 

public static ArrayList<ArrayList<Integer>> permute(int[] array, int k) 
{ 
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 
    ArrayList<Integer> cur = new ArrayList<Integer>(); 
    boolean[] status = new boolean[k]; 
    for (int i = 0; i < k; i++) 
    { 
    status[i] = false; 
    } 
    _permute(res, cur, k, status, array); 
    return res; 
    //code here 
} 

你可以得到陣列的所有排列在數組列表。我想你可以自己從列表中提取數組。並且要小心，如果原始數組中有相同的數字，此功能可以消除重複。

Answer 3

public static void swap(int[] array, int i, int j) { 
    int temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
} 

public static void permute(int[] array, List<int[]> cache, int k) 
{ 

    if (k == array.length-1) 
    { 
     cache.add(array.clone()); //use clone, or you will get the same int array 
     return; 
    } 
    for(int i=k; i<array.length; i++) 
    { 
     swap(array, i,k); 
     permute(array, cache, k+1); 
     swap(array, i, k); 
    } 
}