# C++ Template for all the Permutation Sequence & Permutation Index 1_2 & Next Permutation & Previous Permutation

• Problem 60 The set [1,2,3,…,n] contains a total of n! unique permutations. Given n and k, return the kth permutation sequence.

``````class Solution {
public:
string getPermutation(int n, int k) {
string result;
string num = "123456789";
vector<int> dp(n, 1);
for (int i = 1; i < n; i++)  dp[i] = dp[i - 1] * i;
k--;
for (int i = n; i >= 1; i--) {
//calculate the number in the current position
int j = k / dp[i - 1];
k %= dp[i - 1];
result.push_back(num[j]);
num.erase(j, 1);
}
return result;
}
};
``````

Permutation Index 1 ---- Given a permutation which contains no repeated number, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.

This problem has a very cool solution , this is the original link to the solution permutation index

Here is the AC c++ implementation

``````class Solution {
public:
/**
* @param A an integer array
* @return a long integer
*/
long long permutationIndex (vector<int> &A) {
long long index = 1;
int position = 2;
long long factor = 1;
for (int i = A.size() - 2; i >= 0; i--) {
int successors = 0;
for(int j = i + 1; j < A.size(); ++j) {
if(A[i] > A[j]) {
successors++;
}
}
index += successors * factor;
factor *= position;
position++;
}
return index;
}
};
``````

Permutation Index 2 ---- Given a permutation which may contain repeated numbers, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.

This problem states that we will meet repeated numbers, so we need to avoid the same number permutation's influence !

``````class Solution {
public:
/**
* @param A an integer array
* @return a long integer
*/
long long permutationIndexII(vector<int>& A) {
long long factorial = 1;
long long index = 1;

for (int i = A.size() - 1; i >= 0; i --) {
//different parts : we need to record the repeated element for the current case
map<int, int> hash;
hash[A[i]] ++;
int successors = 0;
for (int j = i + 1; j < A.size(); j ++) {
hash[A[j]] ++;
if (A[j] < A[i]) successors ++;
}
//the original method divide the repeated cases
index += successors * factorial / getRepeatNum(hash);
factorial *= (A.size() - i);
}
return index;
}

// compute all the repeated cases
long long getRepeatNum(map<int,int>& hash) {
long long res = 1;
for (auto i = hash.begin(); i != hash.end(); i ++) {
res *= getFact(i->second);
}
return res;
}

// get the fact for number num
long long getFact(int num) {
long long res = 1;
for (int i = 0; i < num; i ++) {
res *= (i+1);
}
return res;
}
};
``````

Previous Permutation --- Given a list of integers, which denote a permutation. Find the previous permutation in ascending order. For [1,3,2,3], the previous permutation is [1,2,3,3] For [1,2,3,4], the previous permutation is [4,3,2,1]

This problem is different from the next permutation in leetcode, Here is a solution post from the Geeks4Geeks

The key points are

• find the largest index i such that nums[i] > nums[i+1]

• find the largest index j such that j > i && nums[j] < nums[i]

• swap(nums[j], nums[i])

• Reverse the sub-array starting at nums[i+1]

``````class Solution {
public:
/**
* @param nums: An array of integers
* @return: An array of integers that's previous permuation
*/
vector<int> previousPermuation(vector<int> &nums) {
int k = -1, l = 0;
// find the largest index i such that nums[i-1]  > nums[i]
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] > nums[i + 1]) {
k = i;
}
}

if (k >= 0) {
// find the largest index j such that j >= i  && nums[j] < nums[i-1]
for (int i = k + 1; i < nums.size(); ++i) {
if (nums[i] < nums[k]) {
l = i;
}
}
swap(nums[k], nums[l]);
}
// Reverse the sub-array starting at nums[i]
reverse(nums.begin() + k + 1, nums.end());
return nums;
}
};

``````

Problem 31 --- Next Permutation Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

The key points are

• find the largest index i such that nums[i] < nums[i+1]

• find the largest index j such that j > i && nums[j] > nums[i]

• swap(nums[j], nums[i])

• Reverse the sub-array starting at nums[i+1]

``````class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k = -1;
//find the largest index i such that nums[i]  < nums[i+1]
for (int i = 0; i < nums.size()-1; i++) {
if (nums[i] < nums[i + 1]) {
k = i;
}
}
if (k == -1) {
reverse(nums.begin(), nums.end());
return;
}
int l = -1;
//find the largest index j such that j > i  && nums[j] > nums[i]
for (int i = nums.size() - 1; i > k; i--) {
if (nums[i] > nums[k]) {
l = i;
break;
}
}
// swap(nums[j], nums[i])
swap(nums[k], nums[l]);
// Reverse the sub-array starting at nums[i+1]
reverse(nums.begin() + k + 1, nums.end());
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.