打印k下一個按字典順序排列的n位數字排列

Question

我想按字典順序從給定的n位數字集合中產生下一個k排列。

初始數組和k給出。 像讓起始陣列是1 2 4 3 然後接下來的3個排列將是 1 3 2 4： 1 3 4 2： 1 4 3 2：

我試圖

static void permute(int arr[], int low, int high) { 
    if (low == high) { 
     printArray(arr); 
     return; 
    } 
    for (int i=low; i<high; i++) { 
     swap(arr, i, low); 
     permute(arr, low+1, high); 
     swap(arr, low, i); 
    } 
} 

static void swap(int arr[], int i, int j) { 
    int t = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = t; 
} 

但這不按照字典順序給出排列。而且我也無法限制下一個k個排列。

Answer 1

我在JAVA中創建了一個解決方案。我不得不使用BigInteger，因爲隨着我們增加數組的長度，排列的數量可能是天文數字。 （對於短陣列，您可以將其更改爲長。）

複雜度僅爲O（n *長度），因此只要您不想計算數百萬個置換，使用這些複雜對象就不是問題。

它也有2種額外的有用的方法：

BigInteger calculatePermutationNumber(Integer[] arr) 

它計算的陣列在這陣列的排列中的詞典順序位置。

Integer[] createNthPermutation(Integer[] arr, BigInteger n) 

它創建給定（排序）數組的第N個排列。所以你可以用它來計算任何排列，不僅是下一個或前一個排列。

該算法本身是在下面的方法：

Integer[][] createNextXPermutation(Integer[] arr, int x) 

的上述方法中沒有檢查輸入參數的有效性。雖然它有一個有趣的副作用：如果你用字串順序中沒有足夠排列的參數調用函數，那麼它將翻轉並從頭開始繼續列出排列。在某些情況下可能有用。 :)

import java.math.BigInteger; 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

/** 
* @author Selindek 
*/ 
public class Permutation { 

    public static void main(String... args) { 

     Integer[] array = new Integer[] { 1, 2, 4, 3 }; 

     int n = 3; 
     Integer[][] result = createNextXPermutation(array, n); 
     for (int i = 0; i < n; i++) { 
      System.out.println(Arrays.asList(result[i])); 
     } 
    } 

    public static Integer[][] createNextXPermutation(Integer[] arr, int x) { 
     Integer[][] ret = new Integer[x][]; 

     BigInteger n = calculatePermutationNumber(arr); 
     Integer digits[] = Arrays.copyOf(arr, arr.length); 
     Arrays.sort(digits); 
     for (int i = 0; i < x; i++) { 
      ret[i] = createNthPermutation(digits, n.add(BigInteger.valueOf(i + 1))); 
     } 
     return ret; 
    } 

    public static BigInteger calculatePermutationNumber(Integer[] arr) { 
     int length = arr.length; 
     Integer digits[] = Arrays.copyOf(arr, length); 
     Arrays.sort(digits); 
     List<Integer> list = new ArrayList<Integer>(Arrays.asList(digits)); 
     BigInteger n = BigInteger.ZERO; 
     for (int i = 0; i < length - 1; i++) { 
      int index = list.indexOf(arr[i]); 
      list.remove(index); 
      n = n.add(BigInteger.valueOf(index)); 
      n = n.multiply(BigInteger.valueOf(length - 1 - i)); 
     } 
     return n; 
    } 

    public static Integer[] createNthPermutation(Integer[] arr, BigInteger n) { 
     int length = arr.length; 
     Integer[] ret = new Integer[length]; 
     List<Integer> list = new ArrayList<Integer>(Arrays.asList(arr)); 
     int[] pos = new int[length]; 

     for (int i = 1; i <= length; i++) { 
      BigInteger[] div = n.divideAndRemainder(BigInteger.valueOf(i)); 
      n = div[0]; 
      pos[length - i] = div[1].intValue(); 
     } 
     for (int i = 0; i < length; i++) { 
      ret[i] = list.remove(pos[i]); 
     } 
     return ret; 
    } 
}