java 给定n和k，返回第k个置换序列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/31216097/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Given n and k, return the kth permutation sequence
提问by explorer
The set [1,2,3,…,n] contains a total of n! unique permutations.
集合 [1,2,3,…,n] 总共包含 n！独特的排列。
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3 ) :
通过按顺序列出和标记所有排列，我们得到以下序列（即，对于 n = 3 ）：
- "123"
- "132"
- "213"
- "231"
- "312"
- "321" Given n and k, return the kth permutation sequence.
- “123”
- “132”
- “213”
- “231”
- “312”
- "321" 给定 n 和 k，返回第 k 个置换序列。
For example, given n = 3, k = 4, ans = "231".
例如，给定 n = 3，k = 4，ans = "231"。
There are multiple solutions out there. But all of them uses either factorial or there complexity is larger than O(n) such as O(n!). If you use factorial and find the number at the position by k/(n-1)!, the problem comes when n is large(n = 100). Here as n is large, (n-1)! overflows and becomes 0. In result, I am getting a divide by zero error...any solution or algorithm for that?
有多种解决方案。但是它们都使用阶乘或复杂度大于 O(n)，例如 O(n!)。如果您使用阶乘并通过 k/(n-1)! 找到位置处的数字，则当 n 很大时（n = 100）就会出现问题。这里因为 n 很大，(n-1)！溢出并变为 0。结果，我得到了除以零错误......任何解决方案或算法？
Here is my code:
这是我的代码：
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);
}
}
回答by samgak
So if I'm reading the question correctly, you want to find the kth permutation, preferrably without using BigIntegers, provided k is not large enough to require a BigInteger.
因此，如果我正确阅读了问题，您想找到第 k 个排列，最好不使用 BigIntegers，前提是 k 不够大以需要 BigInteger。
If we look at the sequence
如果我们看序列
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
We can rewrite it so that the number in each position is an index into a list of the numbers that haven't appeared so far on the line:
我们可以重写它，使每个位置的数字成为该行迄今为止尚未出现的数字列表的索引：
0 0 0
0 1 0
1 0 0
1 1 0
2 0 0
2 1 0
So for example "2, 0, 0" means start with the list "1, 2, 3", then take the third (because we are indexing from zero), which is a 3, then take the first of the remaining digits "1, 2" which is a 1, then the first of the remaining digit, which is "2". So it produces "3, 1, 2".
例如，“2, 0, 0”表示从列表“1, 2, 3”开始，然后取第三个（因为我们从零开始索引），即 3，然后取剩余数字中的第一个“ 1、2”即是一个1，那么剩下的第一个数字，即“2”。所以它产生“3,1,2”。
To generate these indices, go from right to left and divide k by 1! for the rightmost two places, then 2! then 3! then 4! etc, and then modulo the result with the number of possible indices in that position, which is 1 for the rightmost, 2 for the second-rightmost etc. You don't have to calculate the factorial each time because you can keep a running product.
要生成这些索引，请从右到左将 k 除以 1！对于最右边的两个位置，然后是 2！然后3！那么4！等，然后用该位置的可能索引数对结果求模，最右边为 1，第二个最右边为 2，等等。您不必每次都计算阶乘，因为您可以保留正在运行的产品.
You can break out of the loop as soon as k divided by the factorial is zero, so you only have to compute factorials up until roughly the size of k multiplied by the last place in which k divided by the factorial is non-zero. If k is too large, you need to switch to BigIntegers.
一旦 k 除以阶乘为零，您就可以跳出循环，因此您只需计算阶乘，直到 k 的大小乘以 k 除以阶乘不为零的最后一个位置。如果 k 太大，则需要切换到 BigIntegers。
Once you have the indices it's pretty straightforward to use them to generate the permutation.
一旦你有了索引，使用它们来生成排列就非常简单了。
Code (k starts from 0, so to find the first pass 0, not 1):
代码（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));
}
output:
输出：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
10000000th permutation for n = 100:
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]
[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 , 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 54 , 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 92, 98, 96, 90, 91, 100, 94, 97, 99, 99, 39 ]
回答by Spektre
Of course there is a need for bigintswith such an interface
当然是需要bigints有这样的接口
when you have n = 100then you have n!permutations which means kis in the range k=<1,n!>
当你有n = 100然后你有n!排列这意味着k在范围内k=<1,n!>
100!=93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
which does not fit into the standard unsigned int
不符合标准 unsigned int
2^32= 4294967296
2^64=18446744073709551616
see Fast exact bigint factorial
if you change the interface a bit you suddenly do not need any bigints anymore
如果你稍微改变一下界面，你会突然不再需要任何bigints
just change APIso it sequentially returns 1st,2nd,3th,...permutation without specifying kso you need something like:
只需更改API，以便它按顺序返回 1st,2nd,3th,... 排列而不指定，k因此您需要类似的东西：
of course this is usable only if your usage of permutation is also sequential. You can also make function previous()to handle algorithms which are almost sequential. For random or non-sequential access you need to use bigints
当然，这只有在您使用排列也是顺序的情况下才可用。您还可以使用函数previous()来处理几乎是顺序的算法。对于随机或非顺序访问，您需要使用bigints
回答by Artem Konovalenkov
The indices for k'th permutation (used in the answer to this question) are the factoradicrepresentation of kand can be calculated without using factorial or running product.
为索引k“个置换（在这个问题的答案使用）是factoradic的表示k，并且可以在不使用或阶乘运行乘积来计算。
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;
}
Of course, the indices array should be padded by 0's from the left so that length of the indices array is equal to number of elements to get the actual indices. Alternatively, the permutation could be applied from the right end.
当然，索引数组应该0从左边用's填充，以便索引数组的长度等于元素数以获得实际索引。或者，可以从右端应用置换。
