permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
49namespace permlib {
50
52template<typename TRANS>
54public:
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; }
75protected:
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;
83private:
84 const boost::shared_ptr<PermutationGroup> m_bsgs;
85 boost::shared_ptr<std::set<dom_int> > m_support;
86};
87
88
89template<typename TRANS>
90AbstractBSGS<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
105template <class TRANS>
106void 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
114template <class TRANS>
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
142template <class TRANS>
144 return this->orbits(boost::counting_iterator<dom_int>(0), boost::counting_iterator<dom_int>(m_bsgs->n));
145}
146
147template <class TRANS>
149 return this->orbits(s.begin(), s.end());
150}
151
152template <class TRANS>
153template<typename Iterator>
154AbstractPermutationGroup::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
179template <class TRANS>
180bool 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
231template <class TRANS>
232std::list<typename TRANS::PERMtype::ptr> AbstractBSGS<TRANS>::generators() const {
233 return m_bsgs->S;
234}
235
236template <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
A high level interface implementing a group represented by a BSGS data structure.
Definition: abstract_bsgs.h:53
std::list< typename TRANS::PERMtype::ptr > generators() const
strong generating set of this permutation group
Definition: abstract_bsgs.h:232
const boost::shared_ptr< PermutationGroup > bsgs() const
BSGS data structure for this permutation group.
Definition: abstract_bsgs.h:74
BSGS< typename TRANS::PERMtype, TRANS > PermutationGroup
typedef for the BSGS type associated with this group
Definition: abstract_bsgs.h:56
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 AbstractGroupType type() const
implementation type of this abstract class
Definition: abstract_bsgs.h:68
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
AbstractBSGS(const boost::shared_ptr< PermutationGroup > &bsgs_, bool computeSupport=true)
constructor
Definition: abstract_bsgs.h:90
virtual OrbitList * orbits() const
computes all orbits
Definition: abstract_bsgs.h:143
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
virtual AbstractPermutationGroup * setStabilizer(const std::vector< dom_int > &s) const
computes the stabilizer of a set
Definition: abstract_bsgs.h:115
A high level interface for a permutation group.
Definition: abstract_permutation_group.h:54
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
base change by conjugation and, if necessary, transpositions
Definition: conjugating_base_change.h:52
algorithm to find the lexicographically minimal set in an orbit
Definition: orbit_lex_min_search.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
stores an orbit in a sorted list
Definition: orbit_list.h:42
implementation of a randomized base transposition algorithm
Definition: random_base_transpose.h:50
void search(BSGS< PERM, TRANSRET > &groupK)
searches for a subgroup and stores it into groupK
Definition: backtrack_search.h:96
subgroup search for a set stabilizer based on classical backtracking
Definition: set_stabilizer_search.h:44
void construct(InputIterator begin, InputIterator end)
initializes search
Definition: set_stabilizer_search.h:71
This class never imposes a restriction on any set.
Definition: abstract_bsgs_helpers.h:60
This class implements both canBeIgnored() and set()
Definition: abstract_bsgs_helpers.h:102
This class implements canBeIgnored() but has a trivial set()
Definition: abstract_bsgs_helpers.h:83
dom_int n
degree of group
Definition: bsgs_core.h:61
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:89
void conjugate(const PERM &g)
conjugate group with a permutation
Definition: bsgs.h:324