给定n和k，return第k个排列序列

Question

集合[1,2,3,…,n]一共有n个！独特的排列。

通过按顺序列出和标记所有排列，我们得到以下序列（即，对于 n = 3 ）：

"123"
"132"
"213"
"231"
"312"
"321" 给定 n 和 k，return 第 k 个排列序列。

例如，给定 n = 3，k = 4，ans = "231"。

有多种解决方案。但是它们都使用阶乘或者复杂度大于 O(n)，例如 O(n!)。如果你使用阶乘并通过 k/(n-1)! 找到该位置的数字，当 n 很大（n = 100）时，问题就来了。这里因为 n 很大，所以 (n-1)！溢出并变为 0。结果，我得到除以零的错误...有什么解决方案或算法吗？

这是我的代码：

public class KthPermutation {
    public String getPermutation(int n, int k) {
        // initialize all numbers
        ArrayList<Integer> numberList = new ArrayList<Integer>();

        for (int i = 1; i <= n; i++) {
            numberList.add(i);
        }
        int fact = 1;   // set factorial of n-1

        for (int i = 1; i <= n-1; i++) {
            fact = fact * i;
        }   

        if ((long) k > (long) fact * n) {
            k = (int) ((long) k - (long) (fact * n));
        }
        k--; // set k to base 0

        StringBuilder result = new StringBuilder();
        result = getP(result, numberList, n, k, fact);
        return result.toString();
    }
    public static StringBuilder getP(StringBuilder result,
                ArrayList<Integer> numberList, int n, int k, int fact) {    
        if (numberList.size() == 1 || n == 1) {
            result.append(numberList.get(0));
            return result;  // return condition
        }
        int number = (k / fact) + 1 ;
        result.append(numberList.get(number - 1));
        numberList.remove(number - 1);
        k = k % fact;  // update k
        fact = fact / (n - 1);
        n--;
        return getP(result, numberList, n, k, fact);
    }
}

Answer 1

当然需要bigints这样的界面

当你有 n = 100 那么你有 n! 个排列，这意味着 k 在 k=<1,n!>

范围内

100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

不符合标准unsigned int

2^32=          4294967296
2^64=18446744073709551616

见Fast exact bigint factorial

如果你稍微改变一下界面，你突然就不再需要任何 bigints

只是改变 API 所以它按顺序 returns 1st,2nd,3th,... 排列而不指定 k 所以你需要类似于：

Generalized Permutation (without repetitions) in C++

当然，只有当您对排列的使用也是顺序的时，这才有用。您还可以使函数 previous() 来处理几乎顺序的算法。对于随机或非顺序访问，您需要使用 bigints

Answer 2

因此，如果我没看错问题，您希望找到第 k 个排列，最好不使用 BigInteger，前提是 k 不够大，不需要 BigInteger。

如果我们看序列

我们可以重写它，使每个位置的数字成为该行迄今为止未出现的数字列表的索引：

因此，例如“2,0,0”表示从列表“1,2,3”开始，然后取第三个（因为我们从零开始索引），即 3，然后取第一个剩余数字的“1, 2”是 1，然后是剩余数字的第一个，是“2”。所以它产生“3,1,2”。

要生成这些索引，请从右到左将 k 除以 1！对于最右边的两个地方，然后是 2！然后3！然后4！等等，然后用该位置可能的索引数对结果求模，最右边为 1，第二个最右边为 2 等。您不必每次都计算阶乘，因为您可以保留运行产品。

只要 k 除以阶乘为零，您就可以跳出循环，因此您只需要计算阶乘直到粗略计算 k 的大小乘以最后一个 k 除以阶乘的位置非零。如果k太大，需要换成BigIntegers。

获得索引后，使用它们生成排列就非常简单了。

代码（k从0开始，所以要找第一遍0，不是1）：

static public void findPermutation(int n, int k)
{
    int[] numbers = new int[n];
    int[] indices = new int[n];

    // initialise the numbers 1, 2, 3...
    for (int i = 0; i < n; i++)
        numbers[i] = i + 1;

    int divisor = 1;
    for (int place = 1; place <= n; place++)
    {
        if((k / divisor) == 0)
            break;  // all the remaining indices will be zero

        // compute the index at that place:
        indices[n-place] = (k / divisor) % place;
        divisor *= place;
    }

    // print out the indices:
    // System.out.println(Arrays.toString(indices));

    // permute the numbers array according to the indices:
    for (int i = 0; i < n; i++)
    {
        int index = indices[i] + i;

        // take the element at index and place it at i, moving the rest up
        if(index != i)
        {
            int temp = numbers[index];
            for(int j = index; j > i; j--)
               numbers[j] = numbers[j-1];
            numbers[i] = temp;
        }
    }

    // print out the permutation:
    System.out.println(Arrays.toString(numbers));
}

Demo

输出：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

n = 100 的第 10000000 次排列：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23、24、25、26、27、28、29、30、31、32、33、34、35、36、37、38、39、40、41、42、43、44、45、46、47、 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 92, 98, 96, 90, 91, 100, 94, 97, 95, 99, 93]

Answer 3

第 k 个排列的索引（用于回答此问题）是 k 的 factoradic 表示，可以在不使用阶乘或 [=19 的情况下计算=]产品。

public static List<Integer> toFactoradic(int x) {
    List<Integer> result = new ArrayList<>();

    for(int i = 1; x > 0; x /= i++) {
        result.add(x % i);
    }

    Collections.reverse(result);
    return result;
}

当然，indices数组应该从左边开始用0填充，这样indices数组的长度等于元素的数量，才能得到实际的索引。或者，可以从右端应用排列。

Answer 4

首先我们可以生成 k 的因式表示，然后使用它生成必要的排列。请参阅 https://en.wikipedia.org/wiki/Factorial_number_system 了解更多详情。

public String getPermutation(int n, int k) {
    LinkedList<Integer> factoradic = new LinkedList<>();
    k=k-1; // because factoradic representation and its mapping to permutation starts from 0
    for(int i=1;i<=n; i++){ // get radix digits for n digits
        factoradic.addFirst(k%i);
        k=k/i;
    }
    
    //System.out.println(factoradic.size());
    List<Integer> numbers = new LinkedList<>();
    for(int i=1;i<=n;i++){
        numbers.add(i);
    }
    StringBuilder str = new StringBuilder();
    for(int x: factoradic){
        // System.out.println(x);
        str.append(String.valueOf(numbers.get(x)));
        numbers.remove(x);
    }
    return str.toString();
}

给定n和k，return第k个排列序列

Given n and k, return the kth permutation sequence

java

algorithm

permutation

backtracking

data-structures