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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment