include/algebramix/permutation.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : permutation.hpp
* DESCRIPTION: Permutations
* COPYRIGHT  : (C) 2009  Joris van der Hoeven
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#ifndef __PERMUTATION_HPP
#define __PERMUTATION_HPP
#include <basix/vector.hpp>
#include <basix/wrap.hpp>


namespace mmx {

/******************************************************************************
* Permutations
******************************************************************************/

inline vector<nat>
id_vector (nat n) {
  vector<nat> v= fill<nat> (n);
  for (nat i=0; i<n; i++) v[i]= i;
  return v;
}

class permutation {
MMX_ALLOCATORS
  vector<nat> v;
public:
  inline vector<nat> operator * () const { return v; }
  inline friend vector<nat> as_vector (const permutation& p) { return p.v; }
  inline friend vector<int> as_vector_int (const permutation& p) {
    return as<vector<int> > (p.v); }
  inline permutation (): v () {}
  inline permutation (const vector<nat>& v2): v (v2) {}
  inline permutation (const vector<int>& v2): v (as<vector<nat> > (v2)) {}
  inline permutation (const nat& k): v (id_vector (k)) {}
  inline permutation (const int& k): v (id_vector (k)) {}
  inline permutation (const permutation& p): v (p.v) {}
  inline nat operator () (nat i) const { return v[i]; }

  template <typename C, typename V> vector<C,V>
  operator () (const vector<C,V>& w) {
    ASSERT (N(v) == N(w), "sizes do not match");
    vector<C,V>  t= w;
    for (nat i= 0; i < N (v); i++) t[v[i]]= w[i];
    return t; }
};

WRAP_WRAPPED_IMPL(inline,permutation);

inline iterator<nat> iterate (const permutation& p) {
  return iterate (as_vector (p)); }
inline iterator<int> iterate_int (const permutation& p) {
  return iterate (as_vector_int (p)); }

inline syntactic
flatten (const permutation& p) {
  return flatten (syntactic ("permutation"), iterate (*p));
}

WRAP_BINARY_IMPL(STMPL,permutation,vector<nat>,"Per","Permutation")

/******************************************************************************
* Basic routines for permutations
******************************************************************************/

inline nat N (const permutation& p) { return N(p.v); }
permutation transposition (nat i, nat j, nat n);
permutation cycle (nat n, int plus= 1);
nat nr_transpositions (const permutation& p);
permutation operator * (const permutation& p1, const permutation& p2);
permutation invert (const permutation& p);

} // namespace mmx
#endif // __PERMUTATION_HPP

---