permutation.h
Go to the documentation of this file.
1 /*
2  -------------------------------------------------------------------
3 
4  Copyright (C) 2006-2017, Andrew W. Steiner
5 
6  This file is part of O2scl.
7 
8  O2scl is free software; you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version.
12 
13  O2scl is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with O2scl. If not, see <http://www.gnu.org/licenses/>.
20 
21  -------------------------------------------------------------------
22 */
23 /* permutation/permute_source.c
24  *
25  * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2007 Brian Gough
26  *
27  * This program is free software; you can redistribute it and/or modify
28  * it under the terms of the GNU General Public License as published by
29  * the Free Software Foundation; either version 3 of the License, or (at
30  * your option) any later version.
31  *
32  * This program is distributed in the hope that it will be useful, but
33  * WITHOUT ANY WARRANTY; without even the implied warranty of
34  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
35  * General Public License for more details.
36  *
37  * You should have received a copy of the GNU General Public License
38  * along with this program; if not, write to the Free Software
39  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
40  * 02110-1301, USA.
41  */
42 #ifndef O2SCL_PERMUTATION_H
43 #define O2SCL_PERMUTATION_H
44 
45 /** \file permutation.h
46  \brief Permutation class and output operator
47 */
48 
49 #include <iostream>
50 #include <cstdlib>
51 #include <string>
52 #include <fstream>
53 #include <sstream>
54 #include <vector>
55 
56 #include <boost/numeric/ublas/vector.hpp>
57 
58 #include <o2scl/vector.h>
59 
60 #ifndef DOXYGEN_NO_O2NS
61 namespace o2scl {
62 #endif
63 
64  /** \brief A class for representing permutations
65 
66  To apply a permutation to a user-specified
67  vector, see \ref o2scl::permutation::apply().
68 
69  */
70  class permutation {
71 
72  protected:
73 
74  size_t size_;
75  boost::numeric::ublas::unbounded_array<size_t> data;
76 
77  public:
78 
79  /// Create a permutation of size \c dim
80  permutation(size_t dim=0) {
81  size_=dim;
82  if (dim>0) data.resize(dim);
83  }
84 
85  /// \name Copy constructors
86  //@{
87  permutation(const permutation &v) {
88  size_=v.size();
89  if (size_>0) data.resize(size_);
90  for(size_t i=0;i<size_;i++) {
91  data[i]=v.data[i];
92  }
93  }
94 
95  permutation& operator=(const permutation &v) {
96 
97  // Check for self-assignment
98  if (this==&v) return *this;
99 
100  size_=v.size();
101  if (size_>0) data.resize(size_);
102  for(size_t i=0;i<size_;i++) {
103  data[i]=v.data[i];
104  }
105  return *this;
106  }
107  //@}
108 
109  ~permutation() {
110  };
111 
112  /** \brief Array-like indexing
113  */
114  size_t &operator[](size_t i) {
115 #if !O2SCL_NO_RANGE_CHECK
116  if (i>=size_) {
117  O2SCL_ERR((((std::string)"Array index ")+szttos(i)+" out of bounds"
118  +" in permutation::operator[]. Size: "+
119  szttos(size_)+
120  " (index should be less than size).").c_str(),exc_eindex);
121  return data[0];
122  }
123 #endif
124  return data[i];
125  }
126 
127  /** \brief Array-like indexing
128  */
129  const size_t &operator[](size_t i) const {
130 #if !O2SCL_NO_RANGE_CHECK
131  if (i>=size_) {
132  O2SCL_ERR((((std::string)"Array index ")+szttos(i)+" out of bounds"
133  +" in permutation::operator[]. Size: "+
134  szttos(size_)+
135  " (index should be less than size).").c_str(),exc_eindex);
136  return data[0];
137  }
138 #endif
139  return data[i];
140  }
141 
142  /** \brief Array-like indexing
143  */
144  size_t &operator()(size_t i) {
145 #if !O2SCL_NO_RANGE_CHECK
146  if (i>=size_) {
147  O2SCL_ERR((((std::string)"Array index ")+szttos(i)+" out of bounds"
148  +" in permutation::operator(). Size: "+
149  szttos(size_)+
150  " (index should be less than size).").c_str(),exc_eindex);
151  return data[0];
152  }
153 #endif
154  return data[i];
155  }
156 
157  /** \brief Array-like indexing
158  */
159  const size_t &operator()(size_t i) const {
160 #if !O2SCL_NO_RANGE_CHECK
161  if (i>=size_) {
162  O2SCL_ERR((((std::string)"Array index ")+szttos(i)+" out of bounds"
163  +" in permutation::operator(). Size: "+
164  szttos(size_)+
165  " (index should be less than size).").c_str(),exc_eindex);
166  return data[0];
167  }
168 #endif
169  return data[i];
170  }
171 
172  /** \brief Get (with optional range-checking) */
173  size_t get(size_t i) const {
174 #if !O2SCL_NO_RANGE_CHECK
175  if (i>=size_) {
176  O2SCL_ERR((((std::string)"Permutation index ")+
177  szttos(i)+" out of bounds"+
178  " in permutation::get(). Size: "+
179  szttos(size_)+
180  " (index should be less than size).").c_str(),exc_eindex);
181  return 0;
182  }
183 #endif
184  return data[i];
185  }
186 
187  /** \brief Set (with optional range-checking) */
188  int set(size_t i, size_t val) {
189 #if !O2SCL_NO_RANGE_CHECK
190  if (i>=size_) {
191  O2SCL_ERR((((std::string)"Permutation index ")+szttos(i)+
192  " out of bounds"+" in permutation::set(). Size: "+
193  szttos(size_)+
194  " (index should be less than size).").c_str(),
195  exc_eindex);
196  }
197 #endif
198  data[i]=val;
199  return 0;
200  }
201 
202  /// Initialize permutation to the identity
203  int init() {
204  for(size_t i=0;i<size_;i++) data[i]=i;
205  return 0;
206  }
207 
208  /** \brief Return permutation size
209 
210  If no memory has been allocated, this will quietly
211  return zero.
212  */
213  size_t size() const {
214  return size_;
215  }
216 
217  /** \brief Allocate memory for a permutation of size \c dim
218  */
219  int allocate(size_t dim) {
220  if (size_!=dim && size_>0) free();
221  size_=dim;
222  if (dim>0) {
223  data.resize(dim);
224  }
225  return 0;
226  }
227 
228  /** \brief Free the memory
229 
230  This function will safely do nothing if used without first
231  allocating memory or if called multiple times in succession.
232  */
233  int free() {
234  if (size_>0) {
235  data.resize(0);
236  size_=0;
237  }
238  return 0;
239  }
240 
241  /// Resize
242  void resize(size_t dim) {
243  free();
244  allocate(dim);
245  }
246  //@}
247 
248  /// Swap two elements of a permutation
249  int swap(const size_t i, const size_t j) {
250  size_t tmp=data[i];
251  data[i]=data[j];
252  data[j]=tmp;
253  return 0;
254  }
255 
256  /// Check to see that a permutation is valid
257  bool valid() const {
258  for(size_t i=0;i<size_;i++) {
259  if (data[i]>size_) return false;
260  for(size_t j=0;j<i;j++) {
261  if (data[i]==data[j]) return false;
262  }
263  }
264  return true;
265  }
266 
267  /// Reverse the permutation
268  int reverse() {
269  size_t i;
270  for (i = 0; i < (size_ / 2); i++){
271  size_t j = size_ - i - 1;
272 
273  size_t tmp = this->data[i] ;
274  this->data[i] = this->data[j] ;
275  this->data[j] = tmp ;
276  }
277  return 0;
278  }
279 
280  /// Compute the inverse of a permutation
282  permutation p(size_);
283  for(size_t i=0;i<size_;i++) {
284  p.data[data[i]]=i;
285  }
286  return p;
287  }
288 
289  /// Apply the permutation to a vector
290  template<class vec_t> int apply(vec_t &v) const {
291  size_t i, k, pk;
292  for(i=0;i<size_;i++) {
293  k=data[i];
294  while (k>i) k=data[k];
295  if (k<i) continue;
296  // Now have k==i, i.e. the least in its cycle
297  pk=data[k];
298  if (pk==i) continue;
299  // Shuffle the elements of the cycle
300  {
301  double t=v[i];
302  while (pk!=i) {
303  double r1=v[pk];
304  v[k]=r1;
305  k=pk;
306  pk=data[k];
307  }
308  v[k]=t;
309  }
310  }
311  return 0;
312  }
313 
314  /// Apply the inverse permutation to a vector
315  template<class vec_t> int apply_inverse(vec_t &v) const {
316  size_t i, k, pk;
317  for(i=0;i<size_;i++) {
318  k=data[i];
319  while (k>i) k=data[k];
320  if (k<i) continue;
321  // Now have k==i, i.e. the least in its cycle
322  pk=data[k];
323  if (pk==i) continue;
324  // Shuffle the elements of the cycle
325  {
326  double t=v[k];
327  while (pk!=i) {
328  double r1=v[pk];
329  v[pk]=t;
330  t=r1;
331  k=pk;
332  pk=data[k];
333  }
334  v[pk]=t;
335  }
336  }
337  return 0;
338  }
339 
340  // End of permutation class
341  };
342 
343  /** \brief Output operator for permutations
344 
345  A space is output between the permutation elements but no
346  space or endline character is output after the last element.
347 
348  If the size is zero, this function outputs nothing and does
349  not call the error handler.
350  */
351  std::ostream &operator<<(std::ostream &os, const permutation &p);
352 
353 #ifndef DOXYGEN_NO_O2NS
354 }
355 #endif
356 
357 #endif
358 
The main O<span style=&#39;position: relative; top: 0.3em; font-size: 0.8em&#39;>2</span>scl O$_2$scl names...
Definition: anneal.h:42
void resize(size_t dim)
Resize.
Definition: permutation.h:242
int reverse()
Reverse the permutation.
Definition: permutation.h:268
permutation inverse() const
Compute the inverse of a permutation.
Definition: permutation.h:281
A class for representing permutations.
Definition: permutation.h:70
std::ostream & operator<<(std::ostream &os, const permutation &p)
Output operator for permutations.
permutation(size_t dim=0)
Create a permutation of size dim.
Definition: permutation.h:80
int free()
Free the memory.
Definition: permutation.h:233
int apply_inverse(vec_t &v) const
Apply the inverse permutation to a vector.
Definition: permutation.h:315
size_t & operator[](size_t i)
Array-like indexing.
Definition: permutation.h:114
size_t size() const
Return permutation size.
Definition: permutation.h:213
const size_t & operator()(size_t i) const
Array-like indexing.
Definition: permutation.h:159
#define O2SCL_ERR(d, n)
Set an error with message d and code n.
Definition: err_hnd.h:273
const size_t & operator[](size_t i) const
Array-like indexing.
Definition: permutation.h:129
size_t & operator()(size_t i)
Array-like indexing.
Definition: permutation.h:144
int init()
Initialize permutation to the identity.
Definition: permutation.h:203
Invalid index for array or matrix.
Definition: err_hnd.h:123
int swap(const size_t i, const size_t j)
Swap two elements of a permutation.
Definition: permutation.h:249
int allocate(size_t dim)
Allocate memory for a permutation of size dim.
Definition: permutation.h:219
bool valid() const
Check to see that a permutation is valid.
Definition: permutation.h:257
std::string szttos(size_t x)
Convert a size_t to a string.
int apply(vec_t &v) const
Apply the permutation to a vector.
Definition: permutation.h:290

Documentation generated with Doxygen. Provided under the GNU Free Documentation License (see License Information).