Shulou(Shulou.com)06/01 Report--

This article introduces the relevant knowledge of "how to realize the k th arrangement of Python". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Title

Give the set [1pm 2pm 3, … , n], whose elements all share n! Species arrangement.

List all the arrangements in order of size and mark them one by one. When n = 3, all are arranged as follows:

"123"

"132"

"213"

"231"

"312"

"321"

Given n and k, return the k th permutation.

Description:

The range of a given n is [1,9].

The range of a given k is [1, n!].

Example 1:

Input: n = 3, k = 3 output: "213"

Example 2:

Input: n = 4, k = 9 output: "2314" problem solving ideas: DFS + pruning

Examine the question first, and it is stated in the title that a given set [1, 2, 3,., n] has n! Arrange in the middle. List all the arrangements in size order, mark them, and then return to the k th arrangement.

So according to the meaning of the topic, the easiest thing for us to think of is to list [1, 2, 3, n] all permutations, and then return to the k permutation, but this may be very inefficient, and there is no need for us to find all permutations.

Here we can first look at the rules, as mentioned at the beginning of the title, listing all the arrangements in order of size. That is to say, the number of n elements combined, in which each element is selected from small to large. For example, example 1:

Input: n = 3, k = 3

In this case, given n is 3, then the number to be combined is 3 digits. The full arrangement here is as follows:

"123"

"132"

"213"

"231"

"312"

"321"

We can find that the first element is selected from 1 and increases gradually. When the first element is determined, the second element is also selected from small to large, such as 123132.

Based on the above analysis, we can find that given n elements

When the first element is determined, the following element has (nmur1)! The number of permutations and combinations in, which means that after the first element is selected, the current branch will be generated (nmur1)! The number of species permutations. By analogy, when the first two elements are determined, the number of permutations that can be generated later is (nmur2)!. So:

When k is greater than the number of permutations that can be generated by the previous branches, we can skip it directly.

When k is less than or equal to the number of permutations generated by the current branch, it means that the answer we are looking for is in a permutation of this branch. At this time, we recursively solve the problem (element by element).

The specific code is as follows.

Class Solution: def getPermutation (self, n: int, k: int)-> str: # factorial array arr = [1 for _ in range (n = 1)] for i in range (2, n = 1): arr [I] = ARR [I-1] * I used = [False for _ in range (n = 1)] def dfs (k Tmp): "" Args: tmp: array of arrangement elements "cnt = len (tmp) if cnt = = n: return '.join (tmp) # permutations # notice here that the number of elements in the array is cnt 0 at the beginning, and # is about to add elements at this time, so remove the current element and calculate the number of subsequent permutations, so the number of permutations is (n-cnt-1)! The corresponding arr [n-cnt-1] arr_num = arr [n-cnt-1] # compare the number of rows between k and the current branch for i in range (1 ): if used [I]: continue if k > arr_num: # pruning # if k is greater than the current number of branches Update k, skip the current branch k-= arr_num continue # otherwise Add the current number to the arrangement tmp.append (str (I)) used [I] = True # continue to select return dfs (k, tmp) return dfs (k, []) "how to achieve the k th arrangement of Python". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.