forked from spaghetti-source/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpermutation_hash.cc
More file actions
80 lines (73 loc) · 1.61 KB
/
permutation_hash.cc
File metadata and controls
80 lines (73 loc) · 1.61 KB
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//
// Permutation Hash
//
// Description:
// hash_perm gives one-to-one correspondence between
// permutations over [0,n) and the integer less than n!.
// unhash_perm is the inverse function of hash_perm.
//
// Algorithm:
// The idea is based on the Fisher-Yates shuffle algorithm:
// while n > 1:
// swap(x[n-1], x[rand() % n]);
// --n;
// For an integer given by a factorial number system:
// hash = d_0 (n-1)! + d_1 (n-2)! + ... + d_{n-1} 0!
// The algorithm computes
// while n > 1:
// swap(x[n-1], x[d_{n-1}]
// --n;
//
// Complexity:
// O(n) time, O(n) space.
//
// Verification:
// self.
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
typedef long long ll;
vector<int> unhash_perm(ll r, int n) {
vector<int> x(n);
iota(all(x), 0);
for (; n > 0; --n) {
swap(x[n-1], x[r % n]);
r /= n;
}
return x;
}
ll hash_perm(vector<int> x) {
int n = x.size();
vector<int> y(n);
for (int i = 0; i < n; ++i) y[x[i]] = i;
ll c = 0, fac = 1;
for (; n > 1; --n) {
c += fac * x[n-1]; fac *= n;
swap(x[n-1], x[y[n-1]]);
swap(y[n-1], y[x[y[n-1]]]);
}
return c;
}
int main() {
int n = 9;
vector<int> x(n);
iota(all(x), 0);
do {
ll r = hash_perm(x);
cout << r << ": ";
auto a = unhash_perm(r, n);
for (int i = 0; i < n; ++i) {
cout << a[i] << " ";
if (a[i] != x[i]) exit(-1);
}
cout << endl;
} while (next_permutation(all(x)));
return 0;
}