给定n和k，返回第k个置换序列 [英] Given n and k, return the kth permutation sequence

问题描述

集合[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 p>

有多种解决方案。但是所有这些都使用阶乘或复杂度大于O（n），如O（n！）。如果您使用因子并在k /（n-1）！位置找到数字，那么当n大（n = 100）时出现问题。这里n为大，（n-1）！溢出并变为0.结果，我被零错误除以...任何解决方案或算法？

这是我的代码：

  public class KthPermutation {
 public String getPermutation（int n，int k）{
 //初始化所有数字
 ArrayList< Integer> numberList = new ArrayList< Integer>（）; （int i = 1; i< = n; i ++）
 
 {
 numberList.add（i）; 
} 
 int fact = 1; （int i = 1; i <= n-1; i ++）{
 fact = fact * i; //设置n-1 
 
的因子
} 
 
 if（（long）k>（long）fact * n）{
k =（int）（（long）k  - （long）（fact * n ））; 
} 
 k--; //将k设置为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 condition 
} 
 int number =（k / fact）+ 1; 
 result.append（numberList.get（number  -  1））; 
 numberList.remove（number  -  1）; 
 k = k％事实; // update k 
 fact = fact /（n-1）; 
 n--; 
返回getP（result，numberList，n，k，fact）; 
} 
} 
  

解决方案

如果我正确地阅读这个问题，那么想要找到第k个排列，最好不要使用BigInteger，只要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 
  / pre> 
 
 
所以例如2，0，0表示从列表1，2，3开始，然后取第三个（因为我们从零），这是一个3，然后取剩余数字1,2中的第一个，即1，然后是剩余数字中的第一位，即2。所以它产生3,1,2。
 
 
 
要生成这些索引，从右到左，除以k！最右边的两个地方，然后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 [] indexes = new int [n]; 
 
 //初始化数字1，2，3 ... 
（int i = 0; i 数字[i] = i + 1; 
 
 int divisor = 1; 
（int place = 1; place< = n; place ++）
 {
 if（（k / divisor）== 0）
 break; //所有剩余的索引将为零
 
 //计算该位置的索引：
 indices [n-place] =（k / divisor）％place; 
除数* = place; 
} 
 
 //打印出索引：
 // System.out.println（Arrays.toString（indices））; 
 
 //根据索引排列数组：
 for（int i = 0; i  {
 int index = indices [i] + i; 
 
 //将元素放在索引处并将其放在我的位置，移动剩下的
 if（index！= i）
 {
 int temp = numbers [指数]; 
 for（int j = index; j> i; j--）
 numbers [j] = numbers [j-1]; 
 numbers [i] = temp; 
} 
} 
 
 //打印出排列：
 System.out.println（Arrays.toString（numbers））; 
} 
  
 演示 
 
 
 
输出：
  [1，2，3] 
 [1，3，2] 
 [2,1,3] 
 [2，3，1] 
 [3，1， 2] 
 [3，2，1] 
  
 10000000th排列n = 100： / p> 
 
 
 [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] 
 
The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3 ) :

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
For example, given 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 position by k/(n-1)!, then problem comes when n is large(n = 100). Here as n is large, (n-1)! overflows and becomes 0. In result, I am getting divide by zero error...any solution or algorithm for that?

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);
    }
}

解决方案
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.

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".

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.

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.

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):
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));
}
Demo

output:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
10000000th permutation for n = 100:

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

                        
这篇关于给定n和k，返回第k个置换序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！