给定n和k，返回第k个排列序列
集合[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 numberList = new ArrayList(); for (int i = 1; i <= n; i++) { numberList.add(i); } int fact = 1; // set factorial of n-1 for (int i = 1; i (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 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); } } 因此，如果我正确地阅读了这个问题，你想找到第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 ]
粗略的是需要具有这种界面的bigints
当你有n=100然后你有n! 排列，这意味着k在k=<1,n!>范围内
100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
它不适合标准的unsigned int
2^32= 4294967296 2^64=18446744073709551616
看快速精确bigint阶乘
如果你稍微改变界面，你突然不再需要任何bigints了
只需更改API ，使其按顺序返回第1，第2，第3，…排列而不指定k因此您需要以下内容：
-
C ++中的广义排列（无重复）
只有在排列的使用也是连续的时，这才可用。 您还可以使函数
previous()来处理几乎是连续的算法。 对于随机或非顺序访问，您需要使用bigints
第k个排列的指数（用于该问题的答案）是k的事实表示，并且可以在不使用因子或运行产品的情况下计算。
public static List toFactoradic(int x) { List result = new ArrayList<>(); for(int i = 1; x > 0; x /= i++) { result.add(x % i); } Collections.reverse(result); return result; }
当然，索引数组应该从左边填充0 ，这样索引数组的长度等于获得实际索引的元素数。 或者，可以从右端应用置换。