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.

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

C++:
01 string getPermutation(int n, int k)
02  {
03      string result;
04     int* A=new int[n];
05     for(int i=0;i<n;i++)
06          A[i]=i+1;
07     for(int i=0;i<k1;i++)
08          next_permutation(A,A+n);
09     for(int i=0;i<n;i++)
10          result.push_back(A[i]+‘0’);
11     return result;
12 }
If STL is not allowed, we can alternatively do it like follows. More importantly, the performance is much better since we do not need to list all the first k permutations!

C++:
01 void swap(int *A, int a, int b)
02 {
03     if(a>=b)
04         return;
05     int tmp=A[b];
06     for(int i=b;i>=a+1;i)
07         A[i]=A[i1];
08     A[a]=tmp;
09 }
10 
11 string getPermutation(int n, int k)
12 {
13        string result;
14        int* A=new int[n];
15        int cnt=1;
16        for(int i=0;i<n;i++){
17            A[i]=i+1;
18            cnt*=i+1;
19        }
20        if(k>cnt)
21            return result;
22        cnt=cnt/n;
23        for(int i=0;i<n;i++){
24            int t=k/cnt;
25            int r=k%cnt;
26            if((r==0)&&(t>0))
27                t;
28            swap(A,i,i+t);
29            result.push_back(A[i]+‘0’);
30            k=kt*cnt;
31            if(i<n1)
32                cnt=cnt/(ni1);
33            else
34                cnt=1;
35        }
36 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s