html/doxygen/permutation_8hpp_source.html

00001
00002 /******************************************************************************
00003 * MODULE     : permutation.hpp
00004 * DESCRIPTION: Permutations
00005 * COPYRIGHT  : (C) 2009  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license and comes WITHOUT
00008 * ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
00009 * If you don't have this file, write to the Free Software Foundation, Inc.,
00010 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00011 ******************************************************************************/
00012
00013 #ifndef __PERMUTATION_HPP
00014 #define __PERMUTATION_HPP
00015 #include <basix/vector.hpp>
00016 #include <basix/wrap.hpp>
00017
00019
00020 namespace mmx {
00021
00022 /******************************************************************************
00023 * Permutations
00024 ******************************************************************************/
00025
00026 inline vector<nat>
00027 id_vector (nat n) {
00028   vector<nat> v= fill<nat> (n);
00029   for (nat i=0; i<n; i++) v[i]= i;
00030   return v;
00031 }
00032
00033 class permutation {
00034 MMX_ALLOCATORS
00035   vector<nat> v;
00036 public:
00037   inline vector<nat> operator * () const { return v; }
00038   inline friend vector<nat> as_vector (const permutation& p) { return p.v; }
00039   inline friend vector<int> as_vector_int (const permutation& p) {
00040     return as<vector<int> > (p.v); }
00041   inline permutation (): v () {}
00042   inline permutation (const vector<nat>& v2): v (v2) {}
00043   inline permutation (const vector<int>& v2): v (as<vector<nat> > (v2)) {}
00044   inline permutation (const nat& k): v (id_vector (k)) {}
00045   inline permutation (const int& k): v (id_vector (k)) {}
00046   inline permutation (const permutation& p): v (p.v) {}
00047   inline nat operator () (nat i) const { return v[i]; }
00048
00049   template <typename C, typename V> vector<C,V>
00050   operator () (const vector<C,V>& w) {
00051     ASSERT (N(v) == N(w), "sizes do not match");
00052     vector<C,V>  t= w;
00053     for (nat i= 0; i < N (v); i++) t[v[i]]= w[i];
00054     return t; }
00055 };
00056
00057 WRAP_WRAPPED_IMPL(inline,permutation);
00058
00059 inline iterator<nat> iterate (const permutation& p) {
00060   return iterate (as_vector (p)); }
00061 inline iterator<int> iterate_int (const permutation& p) {
00062   return iterate (as_vector_int (p)); }
00063
00064 inline syntactic
00065 flatten (const permutation& p) {
00066   return flatten (syntactic ("permutation"), iterate (*p));
00067 }
00068
00069 WRAP_BINARY_IMPL(STMPL,permutation,vector<nat>,"Per","Permutation")
00070
00071 /******************************************************************************
00072 * Basic routines for permutations
00073 ******************************************************************************/
00074
00075 inline nat N (const permutation& p) { return N(p.v); }
00076 permutation transposition (nat i, nat j, nat n);
00077 permutation cycle (nat n, int plus= 1);
00078 nat nr_transpositions (const permutation& p);
00079 permutation operator * (const permutation& p1, const permutation& p2);
00080 permutation invert (const permutation& p);
00081
00082 } // namespace mmx
00083 #endif // __PERMUTATION_HPP