给定n和k,返回第k个排列序列

Question

集合[1,2,3,...,n]总共包含n!独特的排列.

通过按顺序列出和标记所有排列,我们得到以下序列(即,对于n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"给定n和k,返回第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

因此,如果我正确地阅读了这个问题,你想要找到第k个排列,最好不使用BigIntegers,只要k不够大就不需要BigInteger.

如果我们看一下序列

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

我们可以重写它,以便每个位置的数字是到目前为止尚未出现的数字列表的索引:

0 0 0
0 1 0
1 0 0
1 1 0
2 0 0
2 1 0

因此,例如"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));
}

演示

输出:

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

n = 100的第1000万次排列:

[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 ]