/
permutation.cpp
114 lines (88 loc) · 2.68 KB
/
permutation.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
#include <cassert>
#include <algorithm>
#include <numeric>
#include "permutation.hpp"
static unsigned int matToPermutationIndex(unsigned int n, unsigned int k, unsigned int i) {
unsigned int ret;
if (i<k)
ret = i;
else if (i<n)
ret = k+n-i-1;
else if (i<n+k)
ret = n+n+k-i-1;
else
ret = i;
return ret;
}
Permutation::Permutation(const Permutation& other) : m_size(other.m_size) {
m_map = new unsigned int[m_size];
std::copy_n(other.m_map, m_size, m_map);
}
Permutation Permutation::Identity(unsigned int size) {
Permutation ret(size);
std::iota(ret.m_map, ret.m_map+ret.m_size, 0);
return ret;
}
Permutation Permutation::operator*(const Permutation& other) const {
assert(m_size==other.m_size);
Permutation ret(m_size);
for (unsigned int i=0; i<m_size; i++) {
ret.m_map[i] = m_map[other[i]];
}
return ret;
}
Permutation& Permutation::preMult(const Permutation& other) {
assert(m_size==other.m_size);
for (unsigned int i=0; i<m_size; i++) {
m_map[i] = other[m_map[i]];
}
return *this;
}
Permutation& Permutation::operator*=(std::pair<unsigned int, unsigned int> p) {
assert(p.first < m_size);
assert(p.second < m_size);
std::swap(m_map[p.first], m_map[p.second]);
return *this;
}
bool Permutation::isIdentity() const {
for (unsigned int i=0; i<m_size; ++i) {
if (m_map[i]!=i) return false;
}
return true;
}
Pairing::Pairing(const FUMatrix& mat, unsigned int k) : m_per(Permutation::Identity(mat.size())) {
assert(k<=mat.size()/2);
for (unsigned int j=1; j<mat.size(); j++) {
for (unsigned int i=0; i<j; i++) {
if (mat(i, j).getCst()) {
const unsigned int a = matToPermutationIndex(mat.size()/2, k, i);
const unsigned int b = matToPermutationIndex(mat.size()/2, k, j);
m_per*=std::make_pair(a, b);
}
}
}
}
void Pairing::swapPoints(std::pair<unsigned int, unsigned int> p) {
m_per *= p;
m_per *= std::make_pair(m_per[p.first], m_per[p.second]);
}
BiPermutation::BiPermutation(const Permutation& per, bool isInverse) : m_per(per), m_inv_per(m_per.size()) {
for (unsigned int i=0; i<m_per.size(); ++i) {
m_inv_per.m_map[m_per[i]] = i;
}
if (isInverse) std::swap(m_per, m_inv_per);
}
BiPermutation::BiPermutation(Permutation&& per, bool isInverse) : m_per(std::move(per)), m_inv_per(m_per.size()) {
for (unsigned int i=0; i<m_per.size(); ++i) {
m_inv_per.m_map[m_per[i]] = i;
}
if (isInverse) std::swap(m_per, m_inv_per);
}
void BiPermutation::preAdd (std::pair<unsigned int, unsigned int> p) {
m_per *= p;
m_inv_per *= std::make_pair(m_per[p.first], m_per[p.second]);
}
void BiPermutation::postAdd(std::pair<unsigned int, unsigned int> p) {
m_per *= std::make_pair(m_inv_per[p.first], m_inv_per[p.second]);
m_inv_per *= p;
}