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
:
"123"
"132"
"213"
"231"
"312"
"321"
Given n
and k
, return the kth
permutation sequence.
Example :
Input: n = 3, k = 3 Output: "213"
Table of Contents
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;
}