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); 
    } 
}