# source:git/gfanlib/gfanlib_symmetry.h@74a91c9

spielwiese
Last change on this file since 74a91c9 was 74a91c9, checked in by Frank Seelisch <seelisch@…>, 13 years ago
new gfan lib version by Anders Jensen git-svn-id: file:///usr/local/Singular/svn/trunk@13668 2c84dea3-7e68-4137-9b89-c4e89433aadc
• Property mode set to `100644`
File size: 4.2 KB
Line
1/*
2 * gfan_symmetry.h
3 *
4 *  Created on: Oct 22, 2010
5 *      Author: anders
6 */
7
8#ifndef GFANLIB_SYMMETRY_H_INCLUDED
9#define GFANLIB_SYMMETRY_H_INCLUDED
10
11#include <set>
12#include "gfanlib_vector.h"
13#include "gfanlib_matrix.h"
14
15namespace gfan{
16
17/**
18 * The permutation class represents an element in the symmetric group S_n.
19 */
20class Permutation:public IntVector
21{
22//  IntVector data;
23public:
24  /**
25   * Returns true if a contains the elements from 0 up to a.size()-1.
26   */
27  static bool isPermutation(IntVector const &a);
28  /**
29   * Generates the identity permutation on n elements.
30   */
31  Permutation(int n):
32    IntVector(n)
33    {
34      for(int i=0;i<n;i++)(*this)[i]=i;
35    }
36  /**
37   * Generates a permutation from the vector v. The ith entry of v tells
38   * If the check flag is set to true, then it is checked whether the vector represents
39   * a permutation. If not, the code fails with an assertion.
40   */
41  Permutation(IntVector const &v, bool check=true):
42    IntVector(v)
43    {
44      if(check)assert(isPermutation(v));
45    }
46
47  static Permutation transposition(int n, int i, int j)
48  {
49    IntVector ret(n);
50    for(int k=0;k<n;k++)ret[k]=k;
51    ret[i]=j;
52    ret[j]=i;
53    return Permutation(ret);
54  }
55  static Permutation cycle(int n)
56  {
57    IntVector a(n);
58    for(int i=0;i<n-1;i++)a[i]=i+1;
59    a[n-1]=0;
60    return Permutation(a);
61  }
62  IntVector toIntVector()const
63  {
64    return IntVector(*this);
65  }
66
67  int sizeOfBaseSet()const
68  {
69    return size();
70  }
71  Permutation inverse()const;
72
73  /**
74   * Apply the permutation
75   */
76  Permutation apply(Permutation const &p)const;
77  IntVector apply(IntVector const &v)const;
78  ZVector apply(ZVector const &v)const;
79  ZMatrix apply(ZMatrix const &m)const;
80  Permutation applyInverse(Permutation const &p)const;
81  IntVector applyInverse(IntVector const &v)const;
82  ZVector applyInverse(ZVector const &v)const;
83  ZMatrix applyInverse(ZMatrix const &m)const;
84
85  /**
86     The set of vectors which are not improved lexicographically when
87     perm is applied to them is convex. Its closure is a
88     halfspace. This routine returns the inner normal of this
89     halfspace. The only exception is if perm is the identity then the
90     zero vector is returned.
91   */
92  ZVector fundamentalDomainInequality()const;
93};
94
95/**
96 * This object represents a subgroup of the symmetric group S_n.
97 */
98
99class SymmetryGroup{
100//  unsigned char *byteTable;
101  int byteTableHeight;
102  class Trie *trie;
103public:
104  typedef std::set<Permutation/*,LexicographicTermOrder*/> ElementContainer;
105   ElementContainer elements;//Make this private
106   int size()const
107   {
108     return elements.size();
109   }
110   int sizeOfBaseSet()const;
111  /**
112     The set of vectors which cannot be improved lexicographically by
113     applying an element from the group is a convex set. Its closure
114     is a polyhedral cone. This routine returns a set of inequalities
115     The returned list does not contain the zero vector.
116   */
117  ZMatrix fundamentalDomainInequalities()const;
118  SymmetryGroup(int n);
119  void computeClosure(Permutation const &v);
120  void computeClosure(ZMatrix const &l);
121  int orbitSize(ZVector const &stable)const;
122  bool isTrivial()const;
123  /**
124     The symmetry group acts on vectors by permuting the entries. The
125     following routine returns a unique representative for the orbit
126     containing v. This makes it easy to check if two elements are in
127     the same orbit. The permutation used to get this representative
128     is stored in *usedPermutation (if pointer not 0).
129   */
130  ZVector orbitRepresentative(ZVector const &v, Permutation *usedPermutation=0)const;
131  /**
132     This routine works as orbitRepresentative() except that the
133     symmetry group considered is only the subgroup keeping the vector
134     fixed fixed.
135   */
136  ZVector orbitRepresentativeFixing(ZVector const &v, ZVector const &fixed)const;
137
138  // Methods for highly optimized symmetry group computations:
139//  void createByteTable();//Can only be called once. SymmetryGroup is not allowed to be changed afterwards or to be copied. Leaks memory at destruction.
140  void createTrie();
141//  unsigned char *getByteTable()const;
142//  int getByteTableHeight()const;
143};
144/**
145 * Sorts v and returns the number of swaps performed.
146 */
147int mergeSort(IntVector &v);
148}
149
150
151
152
153#endif /* GFAN_SYMMETRY_H_ */
Note: See TracBrowser for help on using the repository browser.