Line data Source code
1 : #ifndef ROUTING_KIT_PERMUTATION_H
2 : #define ROUTING_KIT_PERMUTATION_H
3 :
4 : #include <routingkit/constants.h>
5 :
6 : #include <vector>
7 : #include <assert.h>
8 : #include <algorithm>
9 :
10 : namespace RoutingKit{
11 :
12 : //
13 : // Applying a permutation p to a vector v consists of computing the vector {v[p[0]], v[p[1]], v[p[2]], ... , v[p[n]]}
14 : //
15 : // Applying a permutation p to the elements of a vector v consists of computing the vector {p[v[0]], p[v[1]], p[v[2]], ... , p[v[n]]}
16 : //
17 :
18 : inline
19 : bool is_permutation(const std::vector<unsigned>&p){
20 : std::vector<bool>found(p.size(), false);
21 : for(unsigned x:p){
22 : if(x >= p.size())
23 : return false;
24 : if(found[x])
25 : return false;
26 : found[x] = true;
27 : }
28 : return true;
29 : }
30 :
31 : inline
32 10595 : std::vector<unsigned>chain_permutation_first_left_then_right(const std::vector<unsigned>&p, const std::vector<unsigned>&q){
33 : assert(is_permutation(p) && "p must be a permutation");
34 : assert(is_permutation(q) && "q must be a permutation");
35 : assert(p.size() == q.size() && "p and q must permute the same number of objects");
36 10595 : std::vector<unsigned>r(p.size());
37 632419 : for(unsigned i=0; i<r.size(); ++i)
38 621824 : r[i] = p[q[i]];
39 10595 : return r;
40 : }
41 :
42 : inline
43 : std::vector<unsigned>chain_permutation_first_right_then_left(const std::vector<unsigned>&p, const std::vector<unsigned>&q){
44 : return chain_permutation_first_left_then_right(q, p);
45 : }
46 :
47 : template<class T>
48 849 : std::vector<T> apply_permutation(const std::vector<unsigned>&p, const std::vector<T>&v){
49 : assert(is_permutation(p) && "p must be a permutation");
50 : assert(p.size() == v.size() && "permutation and vector must have the same size");
51 :
52 849 : std::vector<T>r(v.size());
53 35089 : for(unsigned i = 0; i<v.size(); ++i)
54 34240 : r[i] = v[p[i]];
55 :
56 849 : return r; // NVRO
57 : }
58 :
59 : template<class T>
60 4245 : std::vector<T> apply_permutation(const std::vector<unsigned>&p, std::vector<T>&&v){
61 : assert(is_permutation(p) && "p must be a permutation");
62 : assert(p.size() == v.size() && "permutation and vector must have the same size");
63 :
64 4245 : std::vector<T>r(v.size());
65 421355 : for(unsigned i = 0; i<v.size(); ++i)
66 417110 : r[i] = std::move(v[p[i]]);
67 :
68 4245 : return r; // NVRO
69 : }
70 :
71 : template<class T>
72 26253 : std::vector<T> apply_inverse_permutation(const std::vector<unsigned>&p, const std::vector<T>&v){
73 : assert(is_permutation(p) && "p must be a permutation");
74 : assert(p.size() == v.size() && "permutation and vector must have the same size");
75 :
76 26253 : std::vector<T>r(v.size());
77 831563 : for(unsigned i = 0; i<v.size(); ++i)
78 805310 : r[p[i]] = v[i];
79 :
80 26253 : return r; // NVRO
81 : }
82 :
83 : template<class T>
84 22039 : std::vector<T> apply_inverse_permutation(const std::vector<unsigned>&p, std::vector<T>&&v){
85 : assert(is_permutation(p) && "p must be a permutation");
86 : assert(p.size() == v.size() && "permutation and vector must have the same size");
87 :
88 22039 : std::vector<T>r(v.size());
89 1033267 : for(unsigned i = 0; i<v.size(); ++i)
90 1011228 : r[p[i]] = std::move(v[i]);
91 :
92 22039 : return r; // NVRO
93 : }
94 :
95 : inline
96 : void inplace_apply_permutation_to_elements_of(const std::vector<unsigned>&p, std::vector<unsigned>&v){
97 : assert(is_permutation(p) && "p must be a permutation");
98 : assert(std::all_of(v.begin(), v.end(), [&](unsigned x){return x < p.size();}) && "v has an out of bounds element");
99 :
100 707908 : for(unsigned i=0; i<v.size(); ++i)
101 688852 : v[i] = p[v[i]];
102 : }
103 :
104 : inline
105 1698 : std::vector<unsigned> apply_permutation_to_elements_of(const std::vector<unsigned>&p, const std::vector<unsigned>&v){
106 : assert(is_permutation(p) && "p must be a permutation");
107 : assert(std::all_of(v.begin(), v.end(), [&](unsigned x){return x < p.size();}) && "v has an out of bounds element");
108 :
109 1698 : std::vector<unsigned> r = v;
110 : inplace_apply_permutation_to_elements_of(p, r);
111 1698 : return r; // NVRO
112 : }
113 :
114 :
115 : inline
116 : void inplace_apply_permutation_to_possibly_invalid_elements_of(const std::vector<unsigned>&p, std::vector<unsigned>&v){
117 : assert(is_permutation(p) && "p must be a permutation");
118 : assert(std::all_of(v.begin(), v.end(), [&](unsigned x){return x < p.size() || x == invalid_id;}) && "v has an out of bounds element");
119 :
120 0 : for(unsigned i=0; i<v.size(); ++i)
121 0 : if(v[i] != invalid_id)
122 0 : v[i] = p[v[i]];
123 : }
124 :
125 : inline
126 : std::vector<unsigned> apply_permutation_to_possibly_invalid_elements_of(const std::vector<unsigned>&p, const std::vector<unsigned>&v){
127 : assert(is_permutation(p) && "p must be a permutation");
128 : assert(std::all_of(v.begin(), v.end(), [&](unsigned x){return x < p.size() || x == invalid_id;}) && "v has an out of bounds element");
129 :
130 : std::vector<unsigned> r = v;
131 : inplace_apply_permutation_to_elements_of(p, r);
132 : return r; // NVRO
133 : }
134 :
135 :
136 : inline
137 849 : std::vector<unsigned> invert_permutation(const std::vector<unsigned>&p){
138 : assert(is_permutation(p) && "p must be a permutation");
139 :
140 849 : std::vector<unsigned> inv_p(p.size());
141 16332 : for(unsigned i=0; i<p.size(); ++i)
142 15483 : inv_p[p[i]] = i;
143 :
144 849 : return inv_p; // NVRO
145 : }
146 :
147 : inline
148 : std::vector<unsigned> identity_permutation(unsigned n){
149 56709 : std::vector<unsigned> p(n);
150 580800 : for(unsigned i=0; i<n; ++i)
151 524091 : p[i] = i;
152 : return p; // NVRO
153 : }
154 :
155 : template<class RandomGenerator>
156 : std::vector<unsigned> random_permutation(unsigned n, RandomGenerator&&gen){
157 : auto r = identity_permutation(n);
158 : std::shuffle(r.begin(), r.end(), std::forward<RandomGenerator>(gen));
159 : return r;
160 : }
161 :
162 : } // RoutingKit
163 :
164 : #endif
165 :
|
