-
Notifications
You must be signed in to change notification settings - Fork 2
/
nth permutation generator.cpp
49 lines (49 loc) · 1.29 KB
/
nth permutation generator.cpp
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
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <map>
const uint16_t MaxFact = 20;
uint64_t fact[MaxFact + 1];
void precomputeFact() {
fact[0] = fact[1] = 1;
for (uint64_t i = 2; i <= MaxFact; ++ i)
fact[i] = fact[i - 1] * i;
}
void getNthPerm(uint16_t len, uint64_t v[], uint64_t n, uint64_t ans[]) {
precomputeFact();
std :: map <uint64_t, uint64_t> fr;
uint16_t i;
for (i = 0; i < len; ++ i)
++ fr[v[i]];
uint64_t div = 1;
std :: map <uint64_t, uint64_t> :: iterator j;
for (j = fr.begin(); j != fr.end(); ++ j)
div *= fact[j -> second];
uint64_t passedPerm = 0, add;
for (i = 0; i < len; ++ i) {
add = 0;
for (j = fr.begin(); j != fr.end() and passedPerm + add < n; ++ j)
add += fact[len - i - 1] / (div / (j -> second));
-- j;
add -= fact[len - i - 1] / (div / (j -> second));
passedPerm += add;
div /= j -> second;
ans[i] = j -> first;
-- fr[j -> first];
if (fr[j -> first] == 0)
fr.erase(j -> first);
}
}
int main() {
std :: ios_base :: sync_with_stdio(false);
std :: cin.tie(nullptr);
uint16_t len, i;
std :: cin >> len;
uint64_t v[len];
for (i = 0; i < len; ++ i)
std :: cin >> v[i];
uint64_t n, ans[len];
std :: cin >> n;
getNthPerm(len, v, n, ans);
for (i = 0; i < len; ++ i)
std :: cout << ans[i] << ' ';
return 0;
}