This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

preface

The sequence of question 60 is as follows:

Give the set [1,2,3… n] in which all elements have n! Kind of arrangement.

All permutations are listed in order of size and marked one by one. When n = 3, all permutations are as follows:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the KTH permutation.

Example 1:

Input: n = 3, k = 3Copy the code

Example 2:

Input: n = 4, k = 9Copy the code

Example 3:

Input: n = 3, k = 1 Output: "123"Copy the code

A, thinking

The topic of arranging a sequence is short and easy to understand. The KTH position in all permutations of the return set [1 to n]

After seeing the topic, MY general thinking is divided into the following two steps:

  1. Recursively generates all permutations, counting each permutation generatedcount++
  2. whencount == kReturns the current result

The pseudocode is shown below:

    int count = 0;
    String ret = "";
    public String getPermutation(int n, int k) {
        dfs("", n, k);
        return ret;
    }

    public void dfs( String path, int n, int k) {
        if (path.length() == n) {
            count++; ret = path;
            return;
        }
        for (int i=1; i<n+1; i++) {
            if (count == k) return;
            if (path.contains(i+"")) continue; dfs(path + i, n, k); }}Copy the code

Until I came across a test case with n = 9 and k = 353955, I tried it for about five times, but it always timed out.

However, I have a question, this code will time out on the force button, but in my local will not have this problem. I guess it may be that the buckle is more strict with the time requirements.

Since recursion cannot solve this problem, a new approach is needed. After reading more than 10 times of the official solution of the force link, I found that I could not understand the official solution of mathematics + reducing the size of the problem.

So I asked my girlfriend, and it told me a very important rule: since the process of selecting numbers goes from left to right, from small to large, the first number in the KTH permutation is (k-1)/(n-1)! Plus 1 is less, and you can do the same thing with the following numbers

How to understand this sentence?

Suppose the KTH permutation is {a1, A2, A3… , an}

And we know that ai as the first number is n minus 1 factorial. So:

  • The first term is the first termP1 = (k-1)/(n-1)! + 1(rounded up, minimum 1) Small number, herepRepresents unselected positions from the left
  • So the second term is the number oneP2 = k - (P1-1)*(n-1)!Small number, because we’re subtracting thetaa1Is all the possibilities of the first number
  • .
  • The firstnThe number for the firstPn = k - (P'n-1' - 1)*(0)!The smaller numbers, I’m subtractingan-1Is the probability of the first number

For example

Take n=4, k=9 as an example

  1. The position of the first term is zeroP1 = 2, so the selection did not select the species2A small number2
  2. We’re dealing with it heren = 3.k = 3(the array is[1, 3, 4]What should I choose as the first number of? At this timeP2 = 2, so choose3
  3. At this point processingn=2.k=1(the array is[1, 4]), availableP3 = 1, so choose1
  4. At this point processingn=1.k=1(the array is[4]), availableP4 = 1, so choose4
  5. In the end the first9An arrangement for2314

So in summary, we only ever care what the first number is (and in the case of the following numbers, the first number of subpermutations to deal with)

Second, the implementation

The implementation code

    public String getPermutation(int n, int k) {
        StringBuilder ret = new StringBuilder();
        int[] factorial = new int[n];   // The factorial of 0 ~ (n-1)
        factorial[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }
        boolean[] selected = new boolean[n+1];
        while (ret.length() < n) {
            // The current number should be selected
            int p = (k - 1) / factorial[n-1-ret.length()] + 1;
            k = k - (p -1) * factorial[n-1-ret.length()];
            int count = 0;
            for (int i=1; i<selected.length; i++) {
                if (selected[i])
                    continue;
                count++;
                if (count == p) {
                    ret.append(i);
                    selected[i] = true;
                    break; }}}return ret.toString();
    }
Copy the code

The test code

    public static void main(String[] args) {
        new Number60().getPermutation(4, 9);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥