Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja
Created October 25, 2016 04:56
Show Gist options
  • Save kartikkukreja/03b184b46ad1f41771a2a170a770cf1c to your computer and use it in GitHub Desktop.
Save kartikkukreja/03b184b46ad1f41771a2a170a770cf1c to your computer and use it in GitHub Desktop.
kth permutation iterative solution
int factorial(int n) {
if (n > 12) return INT_MAX;
int f = 1;
for (int i = 2; i <= n; i++)
f *= i;
return f;
}
string getPermutation(int n, int k) {
k--; // 0-based indexing
if (k >= factorial(n)) return ""; // error
vector<int> num(n);
for (int i = 0; i < n; i++)
num[i] = i+1;
stringstream perm;
for (int i = 0; i < n; i++) {
int fact = factorial(n-i-1);
int incr = k / fact;
int t = num[i+incr];
for (int j = i+incr; j > i; j--)
num[j] = num[j-1];
num[i] = t;
k %= fact;
perm << to_string(num[i]);
}
return perm.str();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment