-
Notifications
You must be signed in to change notification settings - Fork 0
/
PermutationSequence.c
39 lines (38 loc) · 1.04 KB
/
PermutationSequence.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
int fact(int n) {
int ans = 1;
while(n != 1) {
ans = ans * n;
--n;
}
return ans;
}
char *getPermutation(int n, int k) {
char *ans = malloc(sizeof(char) * (n + 1));
ans[n] = '\0';
int currentSize = n;
char currentList[n];
int currentCounter = 0;
for(int i = 1; i < n + 1; ++i) currentList[i - 1] = i + '0';
while(currentSize != 1) {
int currentfact = fact(currentSize - 1);
int index = (k - 1) / currentfact;
ans[currentCounter] = currentList[index];
--currentSize;
for(int i = index; i < currentSize; ++i) currentList[i] = currentList[i + 1];
++currentCounter;
k = k % currentfact;
if (k == 0) {
for(int i = currentSize - 1; i >= 0; --i) {
ans[currentCounter] = currentList[i];
++ currentCounter;
}
return ans;
}
}
ans[currentCounter] = currentList[0];
return ans;
}