permlib  0.2.9
Library for permutation computations
abstract_bsgs.h
1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2012 Thomas Rehn <thomas@carmen76.de>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 // 1. Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // 3. The name of the author may not be used to endorse or promote products
17 // derived from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // ---------------------------------------------------------------------------
31 
32 #include <boost/shared_ptr.hpp>
33 #include <boost/scoped_ptr.hpp>
34 #include <boost/iterator/counting_iterator.hpp>
35 
36 #include <algorithm>
37 
38 #include <permlib/abstract_permutation_group.h>
39 #include <permlib/abstract_bsgs_helpers.h>
40 
41 #include <permlib/change/random_base_transpose.h>
42 #include <permlib/change/conjugating_base_change.h>
43 #include <permlib/search/classic/set_stabilizer_search.h>
44 #include <permlib/search/orbit_lex_min_search.h>
45 
46 #ifndef ABSTRACT_BSGS_H_
47 #define ABSTRACT_BSGS_H_
48 
49 namespace permlib {
50 
52 template<typename TRANS>
54 public:
58 
62  AbstractBSGS(const boost::shared_ptr<PermutationGroup>& bsgs_, bool computeSupport = true);
63 
64  virtual AbstractPermutationGroup* setStabilizer(const std::vector<dom_int>& s) const;
65  virtual OrbitList* orbits() const;
66  virtual OrbitList* orbits(const std::vector<dom_int>& s) const;
67  virtual bool isLexMinSet(const std::vector<dom_int>& setIndices, const std::vector<dom_int>& rankIndices) const;
68  virtual AbstractGroupType type() const { return AGT_BSGS; }
69 
71  std::list<typename TRANS::PERMtype::ptr> generators() const;
72 
74  const boost::shared_ptr<PermutationGroup> bsgs() const { return m_bsgs; }
75 protected:
76  virtual void transversalSizes(std::vector<unsigned long>& sizes) const;
77 
78  template<typename Iterator>
79  OrbitList* orbits(Iterator begin, Iterator end) const;
80 
82  helpers::BaseSupportRestriction* supportRestriction(const std::vector<dom_int>& s) const;
83 private:
84  const boost::shared_ptr<PermutationGroup> m_bsgs;
85  boost::shared_ptr<std::set<dom_int> > m_support;
86 };
87 
88 
89 template<typename TRANS>
90 AbstractBSGS<TRANS>::AbstractBSGS(const boost::shared_ptr<PermutationGroup>& bsgs_, bool computeSupport)
91  : m_bsgs(bsgs_)
92 {
93  if ( ! computeSupport )
94  return;
95 
96  m_support.reset( new std::set<dom_int>() );
97  BOOST_FOREACH(const typename TRANS::PERMtype::ptr& p, m_bsgs->S) {
98  for (dom_int i = 0; i < m_bsgs->n; ++i) {
99  if (p->at(i) != i)
100  m_support->insert(i);
101  }
102  }
103 }
104 
105 template <class TRANS>
106 void AbstractBSGS<TRANS>::transversalSizes(std::vector<unsigned long>& sizes) const {
107  sizes.clear();
108  sizes.reserve(m_bsgs->U.size());
109  BOOST_FOREACH(const TRANS &Ui, m_bsgs->U) {
110  sizes.push_back(Ui.size());
111  }
112 }
113 
114 template <class TRANS>
115 AbstractPermutationGroup* AbstractBSGS<TRANS>::setStabilizer(const std::vector<dom_int>& s) const {
116  if (s.empty())
117  return new AbstractBSGS<TRANS>(*this);
118 
119  boost::scoped_ptr<helpers::BaseSupportRestriction> supRestriction( supportRestriction(s) );
120  if ( supRestriction->canBeIgnored() )
121  return new AbstractBSGS<TRANS>(*this);
122  const std::vector<dom_int>* setToStabilize = supRestriction->set();
123  BOOST_ASSERT( setToStabilize );
124 
125  typedef typename TRANS::PERMtype PERM;
126  PermutationGroup copy(*m_bsgs);
127  // change the base so that is prefixed by the set
128  ConjugatingBaseChange<PERM, TRANS,
129  RandomBaseTranspose<PERM, TRANS> > baseChange(copy);
130  baseChange.change(copy, setToStabilize->begin(), setToStabilize->end());
131 
132  // prepare search without DCM pruning
133  classic::SetStabilizerSearch<BSGS<PERM, TRANS>, TRANS> backtrackSearch(copy, 0);
134  backtrackSearch.construct(setToStabilize->begin(), setToStabilize->end());
135 
136  // start the search
137  boost::shared_ptr<PermutationGroup> stabilizer(new PermutationGroup(copy.n));
138  backtrackSearch.search(*stabilizer);
139  return new AbstractBSGS<TRANS>(stabilizer, m_support);
140 }
141 
142 template <class TRANS>
144  return this->orbits(boost::counting_iterator<dom_int>(0), boost::counting_iterator<dom_int>(m_bsgs->n));
145 }
146 
147 template <class TRANS>
149  return this->orbits(s.begin(), s.end());
150 }
151 
152 template <class TRANS>
153 template<typename Iterator>
154 AbstractPermutationGroup::OrbitList* AbstractBSGS<TRANS>::orbits(Iterator begin, Iterator end) const {
155  OrbitList* retList = new OrbitList();
156 
157  for (Iterator it = begin; it != end; ++it) {
158  const dom_int& alpha = *it;
159  bool knownElement = false;
160  BOOST_FOREACH(const std::set<dom_int>& orb, *retList) {
161  if (orb.find(alpha) != orb.end()) {
162  knownElement = true;
163  break;
164  }
165  }
166 
167  if (knownElement)
168  continue;
169 
170  typedef typename TRANS::PERMtype PERM;
171  OrbitSet<PERM,dom_int> orbit;
172  orbit.orbit(alpha, m_bsgs->S, typename Transversal<PERM>::TrivialAction());
173  retList->push_back(std::set<dom_int>(orbit.begin(), orbit.end()));
174  }
175 
176  return retList;
177 }
178 
179 template <class TRANS>
180 bool AbstractBSGS<TRANS>::isLexMinSet(const std::vector<dom_int>& setIndices, const std::vector<dom_int>& rankIndices) const {
181  if (setIndices.empty())
182  return true;
183 
184  boost::scoped_ptr<helpers::BaseSupportRestriction> supRestriction( supportRestriction(setIndices) );
185  if ( supRestriction->canBeIgnored() )
186  return true;
187  const std::vector<dom_int>* setToLexMin = supRestriction->set();
188  BOOST_ASSERT( setToLexMin );
189 
190  typedef typename TRANS::PERMtype PERM;
191  const unsigned int n = m_bsgs->n;
192 
193  // compute a permutation that we can use for conjugation
194  typename PERM::perm conjugatingPerm(n);
195 
196  // rank indices shall be mapped to 1,2,3,4,5,...
197  unsigned int i = 0;
198  dset rankSet(n);
199  for (std::vector<dom_int>::const_iterator it = rankIndices.begin(); it != rankIndices.end(); ++it)
200  {
201  conjugatingPerm[*it] = i;
202  rankSet[*it] = 1;
203  ++i;
204  }
205 
206  // fill up the rest arbitrarily so that we get a proper permutation
207  unsigned int v = 0;
208  for ( ; i < n; ++i )
209  {
210  while (rankSet[v])
211  ++v;
212  conjugatingPerm[v] = i;
213  ++v;
214  }
215 
216  PERM c(conjugatingPerm);
217  PermutationGroup conjugatedBSGS(*m_bsgs);
218  conjugatedBSGS.conjugate(c);
219 
220  dset rankedTestSet(n);
221  for (std::vector<dom_int>::const_iterator it = setToLexMin->begin(); it != setToLexMin->end(); ++it)
222  {
223  rankedTestSet[c / *it] = 1;
224  }
225 
226  OrbitLexMinSearch<PermutationGroup> orbLexMin(conjugatedBSGS, true);
227  const bool t = ( orbLexMin.lexMin(rankedTestSet) == rankedTestSet );
228  return t;
229 }
230 
231 template <class TRANS>
232 std::list<typename TRANS::PERMtype::ptr> AbstractBSGS<TRANS>::generators() const {
233  return m_bsgs->S;
234 }
235 
236 template <class TRANS>
238  BOOST_ASSERT( m_bsgs );
239  if ( ! m_support )
240  return new helpers::BaseSupportRestriction(m_support, s);
241 
242  // don't use full support restriction if the group base is small
243  if (m_bsgs->B.size() <= 10 )
244  return new helpers::ReducedSupportRestriction(m_support, s);
245 
246  return new helpers::FullSupportRestriction(m_support, s);
247 }
248 
249 } // end NS permlib
250 
251 #endif
BSGS< typename TRANS::PERMtype, TRANS > PermutationGroup
typedef for the BSGS type associated with this group
Definition: abstract_bsgs.h:56
dom_int n
degree of group
Definition: bsgs_core.h:61
virtual void transversalSizes(std::vector< unsigned long > &sizes) const
fills a list with sizes of transversals along a stabilizer chain
Definition: abstract_bsgs.h:106
implementation of a randomized base transposition algorithm
Definition: random_base_transpose.h:50
base change by conjugation and, if necessary, transpositions
Definition: conjugating_base_change.h:52
dset lexMin(const dset &element, const BSGSIN *stabilizer=NULL)
searches the lexicographically minimal element of an orbit
Definition: orbit_lex_min_search.h:124
This class never imposes a restriction on any set.
Definition: abstract_bsgs_helpers.h:60
void search(BSGS< PERM, TRANSRET > &groupK)
searches for a subgroup and stores it into groupK
Definition: backtrack_search.h:96
virtual OrbitList * orbits() const
computes all orbits
Definition: abstract_bsgs.h:143
This class implements canBeIgnored() but has a trivial set()
Definition: abstract_bsgs_helpers.h:83
A high level interface implementing a group represented by a BSGS data structure. ...
Definition: abstract_bsgs.h:53
void conjugate(const PERM &g)
conjugate group with a permutation
Definition: bsgs.h:323
This class implements both canBeIgnored() and set()
Definition: abstract_bsgs_helpers.h:102
subgroup search for a set stabilizer based on classical backtracking
Definition: set_stabilizer_search.h:44
const boost::shared_ptr< PermutationGroup > bsgs() const
BSGS data structure for this permutation group.
Definition: abstract_bsgs.h:74
virtual bool isLexMinSet(const std::vector< dom_int > &setIndices, const std::vector< dom_int > &rankIndices) const
checks whether a set is lexicographically minimal with respect to a given ordering of indices ...
Definition: abstract_bsgs.h:180
virtual AbstractPermutationGroup * setStabilizer(const std::vector< dom_int > &s) const
computes the stabilizer of a set
Definition: abstract_bsgs.h:115
std::list< std::set< dom_int > > OrbitList
typedef for a list of orbits, each of which is a set
Definition: abstract_permutation_group.h:74
virtual AbstractGroupType type() const
implementation type of this abstract class
Definition: abstract_bsgs.h:68
AbstractBSGS(const boost::shared_ptr< PermutationGroup > &bsgs_, bool computeSupport=true)
constructor
Definition: abstract_bsgs.h:90
algorithm to find the lexicographically minimal set in an orbit
Definition: orbit_lex_min_search.h:52
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
helpers::BaseSupportRestriction * supportRestriction(const std::vector< dom_int > &s) const
returns a strategy to decide whether the action of this group is trivial on /s/
Definition: abstract_bsgs.h:237
stores an orbit in a sorted list
Definition: orbit_list.h:42
A high level interface for a permutation group.
Definition: abstract_permutation_group.h:54
void construct(InputIterator begin, InputIterator end)
initializes search
Definition: set_stabilizer_search.h:71
std::list< typename TRANS::PERMtype::ptr > generators() const
strong generating set of this permutation group
Definition: abstract_bsgs.h:232
Definition: abstract_bsgs.h:49