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):

1. "123"

2. "132"

3. "213"

4. "231"

5. "312"

6. "321"

Given n and k, return the kth permutation sequence.

1 public class Solution {
 2     
 3     public String getPermutation(int n, int k) {
 4         int num[] = new int[n];
 5         for(int i = 1; i <= num.length; i++){
 6             num[i - 1] = i;
 7         }//初始化數組
 8         for(int i = 1; i < k; i++){
 9             nextPermutation(num);
10         }//for
11         String result = "";
12         for(int i = 0; i < num.length; i++){
13             result += String.valueOf(num[i]);
14         }
15         
16         return result;
17     }
18     
19     /**
20      * 擷取下一個排列
21      * @param num
22      */
23     private void nextPermutation(int[] num) {
24         if(num.length == 0 || num.length == 1)
25             return;
26         boolean found = false;
27         int index = 0;
28         int comparaValue = 0;
29         for(int i = num.length - 1; i > 0; i--){        //找出出現降序的位置
30             if(num[i] > num[i - 1]){                    //這裡不能交換
31                 index = i;
32                 comparaValue = i - 1;
33                 break;
34             }//if
35         }//for
36 
37             int min = index;
38             for(int i = min; i < num.length; i++){
39                 if(num[i] > num[comparaValue] && num[i] < num[min]){
40                     min = i;
41                 }//if                
42             }//for
43             int temp = num[min];
44             num[min] = num[comparaValue];
45             num[comparaValue] = temp;
46             
47             //對index後面的進行升序排列
48             for(int i = index; i < num.length; i++){
49                 min = i;
50                 for(int j = i + 1; j < num.length; j++){
51                     if(num[min] > num[j])
52                         min = j;
53                 }//for
54                 if(min != i){
55                     temp = num[min];
56                     num[min] = num[i];
57                     num[i] = temp;
58                 }
59             }
60         
61     }
62 }