のn桁の数字の印刷のk次の順列が

Question

私は辞書順にn桁の与えられたセットから次のk個の順列を生成したかったです。

初期配列とkが与えられます。 iは

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

が、この試み

： 1 2 3 4： 1 4 3 2等 は、次の3個の順列が 1 3 2 4あろう出発アレイ1 2 4 3 であるものとします辞書順に並び替えを行っていない。私は次の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; 
    } 
}