Permutation Sequence

Problem

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.

Note: Given n will be between 1 and 9 inclusive.

---

Idea

• 这个题目的思路就是对于这个n位数的排列组合，从最高位到最低位分别确定第kth个数的每一位分别是多少，然后将每一位整合起来。得到那个kth数。可是如何判断每一位是多少呢？
• 以最高位（第n位）为例，最高位有n种情况，每一种情况中，从1到n-1位有（n-1)!种情况，这样，这个n位数的排列组合就被分成了n份，每一份包含了（n-1)!种组合。依次类推若第n位和第n-1都确定，则剩下的排列组合被分成了（n-2)!种情况。
• 若n=6 [1,2,3...,6] k=250, 首先确定最高位，此时排列组合可被分为6份，每份有5!=120. k/120= 250/120 = 2, 所以k在第三组，我们可以得出最高位为3.剩下的set为[1,2,4,5,6]，这时我们要更新k，因为剩下的数是在[1-120]之间了， k=k%5!＝10. 接下来确定第5位，每份有4!=24个组合，则10/24=0，所以k在第1组，这时set中第一个元素为1，所以第5位为1.接下来更新k然后继续上面的步骤，直到确定所有位。

---

Note

• How to add a digit number into string

Solution

---