Leetcode Permutation Sequence Problem Solution

In this Leetcode Permutation Sequence Problem Solution 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 for n = 3:

"123"

"132"

"213"

"231"

"312"

"321"

Given n and k, return the kth permutation sequence.

Leetcode Permutation Sequence Problem Solution


Problem solution in Python.

class Solution(object):
    def getPermutation(self, n, k):
        r = ''; fac = [1]*(n+1); s = []
        for i in xrange(1, n+1):
            fac[i] = i*fac[i-1]
            s.append(i)
        for i in xrange(n, 0, -1):
            ind = (k-1)/fac[i-1]
            r += str(s[ind])
            del s[ind]
            k %= fac[i-1]
        return r

Problem solution in Java.

class Solution {
String result;
int K = 0;
public String getPermutation(int n, int k) 
{
    int[] counts = new int[10];
    for(int i = 1; i <=n; i++)
    {
        counts[i] = 1;    
    }
    
    K = k;
    dfs(counts, n, new StringBuilder());
    return result;
}
 
void dfs(int[] counts, int n, StringBuilder sb)
{
    if(sb.length() == n)
    {
        K = K-1;
        
        if(K == 0)
        {
            result = sb.toString();
            return;
        }
    }
    
    for(int i = 1; i < counts.length; i++)
    {
        if(counts[i] > 0)
        {
            sb.append(String.valueOf(i));
            counts[i]--;
            
            dfs(counts, n, sb);
            
            sb.deleteCharAt(sb.length()-1);
            counts[i]++;
        }
    }
    
}
 
}


Problem solution in C++.

void nextPermutation(string &s)
    {
        int n=s.size();
        
        int idx1=n-1;
        
        while(idx1>0&&((s[idx1]-'0')<(s[idx1-1]-'0')))
        {
            idx1--;
        }
        idx1--;
        
        int j=n-1;
        while((s[idx1]-'0')>(s[j]-'0'))
        {
            j--;
        }
        swap(s[idx1],s[j]);
        
        j=n-1;
        idx1++;
        while(idx1<=j)
        {
            swap(s[idx1],s[j]);
            j--;
            idx1++;
        }
        
    }
    
    string getPermutation(int n, int k) {
        
        string s="";
        
        for(char z='1';z<=n+'0';z++)
        {
            s+=z;
        }
 
        for(int z=1;z<k;z++)
        {
            nextPermutation(s);
        }
        return s;
        
    }


Problem solution in C.

char * getPermutation(int n, int k){
    int anscnt=0;
    char *ans=malloc(sizeof(char)*(n+1));
    ans[n]='\0';// for C you need to care about the end of the string , or you will get RE
    if(n==1){
        ans[0]='1';
        return ans;
    }
    int picked[n+1];
    memset(picked,0,sizeof(int)*(n+1));
    int factorial=1;
    for(int i=2;i<=n;i++){
        //calculate the factorial or all number first, so we only need O(N) time on each factorial
        factorial*=i;
    }
    for(int i=n-1;i>=1;i--){
        factorial/=(i+1);// for each i , the factorial of it
        int max,loccnt=0;
        //max : subproblem answer's first number  
        if(k%factorial==0){
            max=k/factorial-1;
        }
        else{
            max=k/factorial;
        }
        k-=(max*factorial);// the index for the next subproblem
        for(int j=1;j<=n;j++){
            //choose the first number of the subproblem
            if(picked[j]==0){
                if(loccnt==max){
                    ans[anscnt++]=j+'0';
                    picked[j]=1;
                    break;
                }
                loccnt++;
            }
        }
        if(k<=1){
            // the rest are the sorted array , so we end the problem
            for(int j=1;j<=n;j++){
                if(picked[j]==0){
                    ans[anscnt++]=j+'0';
                }
            }
            break;
        }
    }
    return ans;
}


Post a Comment

0 Comments