# 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"```

## 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++)
{
}
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;
}``````