-
Notifications
You must be signed in to change notification settings - Fork 0
/
utils.cpp
138 lines (115 loc) · 4.02 KB
/
utils.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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include "utils.h"
#include <boost/iterator/counting_iterator.hpp>
// Slightly pollute permlib namespace for this...
namespace permlib {
std::size_t hash_value(const Permutation& perm) {
// Permutation is backed by std::vector, but with fewer public accessors.
// So we just copy hash_value(std::vector)
std::size_t seed = 0;
for (int i = 0; i < perm.size(); ++i) {
boost::hash_combine(seed, perm.at(i));
}
return seed;
}
}
/* FUNCTIONS THAT ARE SYNTACTIC SUGAR ********************************************************** */
/**
* Creates the set {0, .., v - 1}, which is how the set X = {1, .., v} is represented internally.
*/
Subset generateX(unsigned int v) {
using boost::counting_iterator;
Subset result;
std::copy(counting_iterator<unsigned long>(0), counting_iterator<unsigned long>(v),
std::inserter(result, result.begin()));
return result;
}
/**
* Creates the set X - B, where B is a subset of X and X = {1, .., v}. As with other X-functions,
* the set X is represented by {0, .., v - 1}, due to permutation's internal representation.
*/
Subset xMinus(unsigned int v, const Subset& B) {
using boost::counting_iterator;
Subset result;
std::set_difference(counting_iterator<int>(0), counting_iterator<int>(v),
B.begin(), B.end(),
std::inserter(result, result.begin()));
return result;
}
/* FUNCTIONS THAT ARE NOT SYNTACTIC SUGAR ****************************************************** */
/**
* Returns a permutation as a list of disjoint cycles.
* In PermLib, a Permutation is stored internally in "list notation", so this is needed.
*/
std::vector<Cycle> permutationCycles(const Permutation& g, int v) {
// Permutation stores {1, .., v} as {0, .., v - 1}
Subset pointsRemaining = generateX(v);
std::vector<Cycle> cycles;
while (!pointsRemaining.empty()) {
Cycle cycle;
unsigned long firstPoint = *(pointsRemaining.begin());
unsigned long nextPoint = firstPoint;
do {
cycle.push_back(nextPoint);
pointsRemaining.erase(pointsRemaining.find(nextPoint));
// Next point in cycle
nextPoint = g.at(nextPoint);
} while (nextPoint != firstPoint);
cycles.push_back(cycle);
}
return cycles;
}
/**
* Partitions the input integer k.
*
* This particular implementation is particularly inefficient for large values of k (as the list
* of partitions grows large), so it should be replaced with one based on a forward iterator.
* In practice, the inputs will tend to be on the small size...
*/
std::set<std::multiset<unsigned int> > partition(unsigned int k) {
if (k == 1) {
std::multiset<unsigned int> singleton;
singleton.insert(1);
std::set<std::multiset<unsigned int> > result;
result.insert(singleton);
return result;
} else {
std::set<std::multiset<unsigned int> > result;
for (int i = 1; i < k; i++) {
// Partition k - i and append i to each result therein
std::set<std::multiset<unsigned int> > smaller = partition(k - i);
for (std::set<std::multiset<unsigned int> >::iterator it = smaller.begin(); it != smaller.end(); it++) {
std::multiset<unsigned int> ms(*it); // Copy the multiset
ms.insert(i);
result.insert(ms);
}
}
// Finally, add the singleton k itself
std::multiset<unsigned int> singleton;
singleton.insert(k);
result.insert(singleton);
return result;
}
}
/**
* Computes the binomial coefficient.
*
* Note that we avoid boost::math::binomial_coefficient() because it's not recommended for
* integer return types (it uses factorials and beta function).
*/
unsigned int combinat(unsigned int n, unsigned int k) {
if (k > n - k) k = n - k; // Symmetry of the binomial coefficient
int result = 1;
for (int i = 0; i < k; i++) {
result *= n - i;
result /= i + 1; // Avoids fractions
}
return result;
}
bool PermutationWeakOrdering::operator()(const Permutation& perm1, const Permutation& perm2) const {
int pos = 0;
for (; pos < perm1.size(); pos++) {
if (pos == perm2.size() || perm2.at(pos) < perm1.at(pos)) return false;
else if (perm1.at(pos) < perm2.at(pos)) return true;
}
return (pos != perm2.size());
}