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

小编典典

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

algorithm

集[1,2,3，…，n]总共包含n！独特的排列。

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

“ 123”
“ 132”
“ 213”
“ 231”
“ 312”
“ 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);
    }
}

阅读 702

2020-07-28

共1个答案

小编典典

因此，如果我正确地阅读了该问题，则希望找到第k个排列，最好不使用BigIntegers，前提是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));
}

演示版

输出：

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

2020-07-28