1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Permutation Sequence
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/permutation-sequence/
7+ Notes:
8+ The set [1,2,3,...,n] contains a total of n! unique permutations.
9+ By listing and labeling all of the permutations in order,
10+ We get the following sequence (ie, for n = 3):
11+ "123"
12+ "132"
13+ "213"
14+ "231"
15+ "312"
16+ "321"
17+ Given n and k, return the kth permutation sequence.
18+ Note: Given n will be between 1 and 9 inclusive.
19+
20+ Solution: 1. Brute!
21+ 2. combinatorial mathematics.
22+ */
23+ public class Solution {
24+ public void nextPermutation (char []num ) {
25+ int last =num .length -1 ;
26+ int i =last ;
27+ while (i >0 &&num [i -1 ] >=num [i ]) --i ;
28+ for (int l =i ,r =last ;l <r ; ++l , --r ) {
29+ num [l ] = (char ) (num [l ] ^num [r ]);
30+ num [r ] = (char ) (num [l ] ^num [r ]);
31+ num [l ] = (char ) (num [l ] ^num [r ]);
32+ }
33+ if (i ==0 ) {
34+ return ;
35+ }
36+ int j =i ;
37+ while (j <=last &&num [i -1 ] >=num [j ]) ++j ;
38+ num [i -1 ] = (char ) (num [i -1 ] ^num [j ]);
39+ num [j ] = (char ) (num [i -1 ] ^num [j ]);
40+ num [i -1 ] = (char ) (num [i -1 ] ^num [j ]);
41+ }
42+ public String getPermutation_1 (int n ,int k ) {
43+ char []num =new char [n ];
44+ for (int i =0 ;i <n ; ++i )num [i ] = (char ) (i +'1' );
45+ System .out .println (String .valueOf (num ));
46+ while (--k !=0 ) {
47+ nextPermutation (num );
48+ }
49+ return String .valueOf (num );
50+ }
51+ public String getPermutation_2 (int n ,int k ) {
52+ StringBuffer sb =new StringBuffer ();
53+ StringBuffer res =new StringBuffer ();
54+ int total =1 ;
55+ for (int i =1 ;i <=n ; ++i ) {
56+ total =total *i ;
57+ sb .append (i );
58+ }
59+ k --;
60+ while (n !=0 ) {
61+ total =total /n ;
62+ int idx =k /total ;
63+ res .append (sb .charAt (idx ));
64+ k =k %total ;
65+ sb .deleteCharAt (idx );
66+ n --;
67+ }
68+ return res .toString ();
69+ }
70+ }
