/Users/mourrain/Devel/mmx/algebramix/src/permutation.cpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : permutation.cpp
* 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.
******************************************************************************/

#include <algebramix/permutation.hpp>


namespace mmx {

permutation
transposition (nat i, nat j, nat n) {
  vector<nat> v= id_vector (n);
  v[i]= j;
  v[j]= i;
  return permutation (v);
}

permutation
cycle (nat n, int plus) {
  if (plus >= 0) plus= ((nat) plus) % n;
  else plus= (n-1) - (((nat) (-1-plus)) % n);
  vector<nat> v= id_vector (n);
  for (nat i=0; i<n; i++)
    if (i + plus < n) v[i]= i + plus;
    else v[i]= i + plus - n;
  return permutation (v);
}

nat
nr_transpositions (const permutation& p) {
  nat s= 0, n= N(p);
  for (nat i=0; i<n; i++)
    if (p (i) > i) s += p (i) - i;
  return s;
}

permutation
operator * (const permutation& p1, const permutation& p2) {
  nat n= N(p1);
  ASSERT (N(p2) == n, "sizes do not match");
  vector<nat> v= fill<nat> (n);
  for (nat i=0; i<n; i++) v[i]= p1 (p2 (i));
  return permutation (v);
}

permutation
invert (const permutation& p) {
  nat n= N(p);
  vector<nat> v= fill<nat> (n);
  for (nat i=0; i<n; i++) v[p(i)]= i;
  return permutation (v);
}

} // namespace mmx