# source:git/gfanlib/gfanlib_symmetry.h@43317d

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