cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
Permutation
(library/util/permutation.hpp)
- View this file on GitHub
- Last update: 2022-04-04 15:10:37+09:00
- Include:
#include "library/util/permutation.hpp" - Link: https://twitter.com/noshi91/status/1452081886025555972?s=20
Permutation
Verified with
Code
#ifndef SUISEN_PERMUTATION
#define SUISEN_PERMUTATION
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
namespace suisen {
struct Permutation : public std::vector<int> {
using base_type = std::vector<int>;
using base_type::base_type;
Permutation() : Permutation(0) {}
Permutation(std::size_t n) : Permutation(int(n)) {}
Permutation(int n) : base_type(n) {
std::iota(begin(), end(), 0);
}
Permutation(const std::vector<int>& a) : std::vector<int>(a) {}
Permutation(std::vector<int>&& a) : std::vector<int>(std::move(a)) {}
// returns b s.t. b[i] = a[p[i]]
template <typename T>
std::vector<T> permute(const std::vector<T>& a) const {
const int n = a.size();
std::vector<T> res(n);
for (int i = 0; i < n; ++i) res[i] = a[(*this)[i]];
return res;
}
// returns b s.t. b[p[i]] = a[i]
template <typename T>
std::vector<T> inv_permute(const std::vector<T>& a) const {
const int n = a.size();
std::vector<T> res(n);
for (int i = 0; i < n; ++i) res[(*this)[i]] = a[i];
return res;
}
// returns p * q s.t. (p * q)[i] = p[q[i]]
friend Permutation operator*(const Permutation& p, const Permutation& q) {
return q.permute(p);
}
Permutation& operator*=(const Permutation& q) {
return *this = *this * q;
}
Permutation inv() const {
const int n = size();
Permutation res(n);
for (int i = 0; i < n; ++i) res[(*this)[i]] = i;
return res;
}
Permutation pow(long long k) const {
assert(k >= 0);
const int n = size();
std::vector<int8_t> seen(n, false);
Permutation res(n);
for (int s = 0; s < n; ++s) {
if (seen[s]) continue;
std::vector<int> cycle { s };
for (int v = (*this)[s]; v != s; v = (*this)[v]) cycle.push_back(v);
const int l = cycle.size();
for (int j = 0; j < l; ++j) {
int v = cycle[j];
seen[v] = true;
res[v] = cycle[(j + k) % l];
}
}
return res;
}
template <typename T, typename Comp = std::less<T>>
static Permutation index_sort(const std::vector<T>& a, Comp comp = Comp{}) {
Permutation p(a.size());
std::sort(p.begin(), p.end(), [&](int i, int j) { return comp(a[i], a[j]); });
return p;
}
};
template <typename hash_t>
struct PermutationHash {
hash_t operator()(const Permutation &p) const {
return hash(p);
}
/**
* minimal perfect hash function for permutations.
* complexity: O(n) time, O(n) extra space
* reference: https://twitter.com/noshi91/status/1452081886025555972?s=20
*/
static hash_t hash(const Permutation &per) {
hash_t h = 0;
const int n = per.size();
Permutation p = per;
Permutation q = per.inv();
for (int i = n - 1; i >= 0; --i) {
h = h * (i + 1) + p[i];
p[q[i]] = p[i];
q[p[i]] = q[i];
}
return h;
}
static Permutation unhash(int n, hash_t h) {
Permutation p = Permutation(n), q = p;
for (int i = 0; i < n; ++i) {
p[i] = h % (i + 1), q[i] = q[p[i]];
q[p[i]] = p[q[i]] = i;
h /= i + 1;
}
return p;
}
};
} // namespace suisen
#endif // SUISEN_PERMUTATION#line 1 "library/util/permutation.hpp"
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
namespace suisen {
struct Permutation : public std::vector<int> {
using base_type = std::vector<int>;
using base_type::base_type;
Permutation() : Permutation(0) {}
Permutation(std::size_t n) : Permutation(int(n)) {}
Permutation(int n) : base_type(n) {
std::iota(begin(), end(), 0);
}
Permutation(const std::vector<int>& a) : std::vector<int>(a) {}
Permutation(std::vector<int>&& a) : std::vector<int>(std::move(a)) {}
// returns b s.t. b[i] = a[p[i]]
template <typename T>
std::vector<T> permute(const std::vector<T>& a) const {
const int n = a.size();
std::vector<T> res(n);
for (int i = 0; i < n; ++i) res[i] = a[(*this)[i]];
return res;
}
// returns b s.t. b[p[i]] = a[i]
template <typename T>
std::vector<T> inv_permute(const std::vector<T>& a) const {
const int n = a.size();
std::vector<T> res(n);
for (int i = 0; i < n; ++i) res[(*this)[i]] = a[i];
return res;
}
// returns p * q s.t. (p * q)[i] = p[q[i]]
friend Permutation operator*(const Permutation& p, const Permutation& q) {
return q.permute(p);
}
Permutation& operator*=(const Permutation& q) {
return *this = *this * q;
}
Permutation inv() const {
const int n = size();
Permutation res(n);
for (int i = 0; i < n; ++i) res[(*this)[i]] = i;
return res;
}
Permutation pow(long long k) const {
assert(k >= 0);
const int n = size();
std::vector<int8_t> seen(n, false);
Permutation res(n);
for (int s = 0; s < n; ++s) {
if (seen[s]) continue;
std::vector<int> cycle { s };
for (int v = (*this)[s]; v != s; v = (*this)[v]) cycle.push_back(v);
const int l = cycle.size();
for (int j = 0; j < l; ++j) {
int v = cycle[j];
seen[v] = true;
res[v] = cycle[(j + k) % l];
}
}
return res;
}
template <typename T, typename Comp = std::less<T>>
static Permutation index_sort(const std::vector<T>& a, Comp comp = Comp{}) {
Permutation p(a.size());
std::sort(p.begin(), p.end(), [&](int i, int j) { return comp(a[i], a[j]); });
return p;
}
};
template <typename hash_t>
struct PermutationHash {
hash_t operator()(const Permutation &p) const {
return hash(p);
}
/**
* minimal perfect hash function for permutations.
* complexity: O(n) time, O(n) extra space
* reference: https://twitter.com/noshi91/status/1452081886025555972?s=20
*/
static hash_t hash(const Permutation &per) {
hash_t h = 0;
const int n = per.size();
Permutation p = per;
Permutation q = per.inv();
for (int i = n - 1; i >= 0; --i) {
h = h * (i + 1) + p[i];
p[q[i]] = p[i];
q[p[i]] = q[i];
}
return h;
}
static Permutation unhash(int n, hash_t h) {
Permutation p = Permutation(n), q = p;
for (int i = 0; i < n; ++i) {
p[i] = h % (i + 1), q[i] = q[p[i]];
q[p[i]] = p[q[i]] = i;
h /= i + 1;
}
return p;
}
};
} // namespace suisen