Permutation Sequence

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.

Analysis

举例：n=3, k=5

• 得到factorial[] = {1,1,2} （算n!，方便后面使用）
• 得到numbers = {1,2,3} (用来加到string里面去的元素)
• k--: k=4
• while循环i从1到3
  • i=1
    • (3-1)!=2, 加上第一个数以后，有两种变换方法
    • 4/2 = 2，加入numbers[2]=3（注意这里k要减一）
    • 从numbers里除去numbers[2],numbers变为{1,2}
    • 4减去2*2 = 0,下一个问题中的第0顺位
  • i=2
    • (3-2)!=1
    • 0/1=0, 加入numbers[0]=1
    • 移除number[0], numbers = {2}
    • 0减去1*0 = 0
  • i=3
    • (3-3)!=1
    • 0/1=0, 加入numbers[0]=2
    • 移除numbers[0]，numbers变为{}
    • 0减去1*0=0

Code

public class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<Integer>();
        int[] factorial = new int[n+1];
        StringBuilder sb = new StringBuilder();

        //create an array of factorial lookup
        int sum = 1;
        factorial[0]=1;
        for(int i=1; i<=n; i++){
            sum *= i;
            factorial[i] = sum;
        }
        //factorial[] = {1,1,2,6}

        for (int i=1; i<=n; i++){
            numbers.add(i);
        }
        //numbers = {1,2,3}

        k--;

        for(int i=1; i<=n; i++){
            int index = k/factorial[n-i];
            sb.append(String.valueOf(numbers.get(index)));
            numbers.remove(index);
            k -= factorial[n-i]*index;
        }

        return sb.toString();
    }
}

Note

• stringBuilder.append(string)
• ArrayList.get(index)
• String.valueOf(object)
• ArrayList.remove(index)
• stringBuilder.toString()

Reference

Leetcode