Permutation Sequence Problem Solution

Permutation Sequence Problem: 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:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Example :

Input: n = 3, k = 3
Output: "213"

Permutation Sequence Problem Solution

Problem Solution In Python

class Solution(object):
    def getPermutation(self, n, k):
        pe=[]
        list=[]
        for i in range(1,n+1):
            list.append(str(i))
        k1=k-1
        n1=n-1
        def fact(m):
            if m==0:
                return 1
            x=1
            for i in range(1,m+1):
                x=x*i
            return x
        while n1>=0:
            a=min(k1/fact(n1),n1)
            
            k1=k1-a*fact(n1)
            n1=n1-1
            pe.append(list[a])
            list.pop(a)
            
        return ''.join(pe)

Problem Solution In Java

public static String getPermutation(int n, int k)
{
    int check=1;
    String str="";
    List<Integer>list=new ArrayList<Integer>();
    for(int i=1;i<=n;i++)
    {
        list.add(i);
    }
    int factorial=factorial(n);
    while(check<=n)
    {
        factorial/=(n-check+1!=0?n-check+1:1);
        int m=k/factorial*factorial!=k?k/factorial+1:k/factorial;
        k=k%factorial!=0?k%factorial:factorial;
        if(m==0)
        {
            str+=list.get(0);
            list.remove(0);
        }
        else
        {
            str+=list.get(m-1);
            list.remove(m-1);
        }
        check++;
    }
    return str;
}
public static int factorial(int n)
{
    int factorial=1;
    for(int i=2;i<=n;i++)
        factorial*=i;
    return factorial;
}

Problem Solution In C++

class Solution {
public:
string getPermutation(int n, int k) {

    char xs[n+1];
    for(int i=1;i<=n;i++)
    {
        char ch=char(i+'0');
        xs[i-1]=ch;
    }
    xs[n]='\0';
    int cnt=0;

    do
    {
        cnt++;

        if(cnt==k)break;
    }
    while (std::next_permutation(xs, xs + sizeof(xs) - 1));
    string ans=xs;
    return ans;
}
};

Problem Solution In C

void swap(char* str, int i, int j) {
    char tmp = str[i];
    str[i] = str[j];
    str[j] = tmp;
}

char * getPermutation(int n, int k){
    char* str = (char*)malloc((n + 1) * sizeof(char));
    memset(str, '\0', (n + 1) * sizeof(char));
    
    for (int i = 0; i < n; i++) {
        str[i] = i + 1 + '0';
    }
    
    for (int i = 0; i < k - 1; i++) {
        int x, y;
        
        for (x = n - 2; x >= 0; x--) {
            if (str[x] < str[x + 1]) {
                break;
            }
        }
        
        for (y = n - 1; y >= x; y--) {
            if (str[y] > str[x]) {
                swap(str, x, y);
                break;
            }
        }
        
        int a = x + 1;
        int b = n - 1;
        
        while (a < b) {
            swap(str, a, b);
            a++; b--;
        }
    }

    return str;
}