通过列出和标记所有的排列顺序,
我们得到以下序列(即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,fact);
}
}
解决方法
如果我们看序列
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”表示从列表“1,3”开始,然后取第三个(因为我们从零索引),这是一个3,然后取第一个剩余的数字“ 1,2“是1,然后是第一个剩余的数字,即”2“.所以它产生“3,1,2”.
要生成这些索引,从右到左,将k除以1！最右边的两个地方,然后2！然后3！然后4！等等,然后用该位置的可能索引的数量模拟结果,最右边为1,最右侧为2等.您不必每次都计算因子,因为您可以保留正在运行的产品.
一旦k除以阶乘为零,你就可以突破循环,所以你只需要计算阶乘,直到大致大小的k乘以k除以阶乘的最后一个地方是非零.如果k太大,则需要切换到BigInteger.
一旦你有了索引,用它来产生排列就是非常简单的.
代码(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,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,3] [1,2] [2,3] [2,1] [3,2] [3,1]
n = 100的10000000次排列：
[1,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 ]
