permlib
0.2.9
Library for permutation computations
|
coset representative search for a lex-smaller set images More...
#include <lex_smaller_image_search.h>
Public Types | |
typedef BacktrackSearch< BSGSIN, TRANSRET >::PERM | PERM |
![]() | |
typedef BaseSearch< BSGSIN, TRANSRET >::PERM | PERM |
typedef BaseSearch< BSGSIN, TRANSRET >::TRANS | TRANS |
![]() | |
typedef BSGSIN::PERMtype | PERM |
typedef BSGSIN::TRANStype | TRANS |
typedef std::list< typename PERM::ptr > | PERMlistType |
Public Member Functions | |
LexSmallerImageSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM) | |
constructor More... | |
template<class InputIteratorZ , class InputIteratorO > | |
void | construct (InputIteratorZ zerosBegin, InputIteratorZ zerosEnd, InputIteratorO onesBegin, InputIteratorO onesEnd) |
initializes search More... | |
![]() | |
BacktrackSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool breakAfterChildRestriction=false, bool stopAfterFirstElement=false) | |
constructor More... | |
void | search (BSGS< PERM, TRANSRET > &groupK) |
searches for a subgroup and stores it into groupK | |
virtual BaseSearch< BSGSIN, TRANSRET >::PERM::ptr | searchCosetRepresentative (BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL) |
searches for a coset representative if one exists More... | |
![]() | |
BaseSearch (const BSGSIN &bsgs, unsigned int pruningLevelDCM, bool stopAfterFirstElement) | |
constructor More... | |
virtual | ~BaseSearch () |
destructor | |
bool | minOrbit (unsigned long alpha, BSGS< PERM, TRANSRET > &groupK, unsigned int i, unsigned long beta_i) const |
finds minimal elements in an orbit More... | |
virtual PERM::ptr | searchCosetRepresentative () |
searches for a coset representative if one exists | |
Additional Inherited Members | |
![]() | |
unsigned long | m_statNodesVisited |
nodes visited during backtrack search | |
unsigned long | m_statNodesPrunedCosetMinimality |
number of nodes where (simple) double coset minimality pruning was in effect | |
unsigned long | m_statNodesPrunedCosetMinimality2 |
number of nodes where advanced double coset minimality pruning with base change was in effect | |
unsigned long | m_statNodesPrunedChildRestriction |
number of nodes where a child constraint pruning was in effect | |
![]() | |
virtual const std::vector< dom_int > & | subgroupBase () const |
base of the sought subgroup | |
void | construct (SubgroupPredicate< PERM > *pred, bool addPredRefinement) |
initializes the search | |
unsigned int | search (const PERM &t, unsigned int level, unsigned int &completed, BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL) |
recursive backtrack search | |
![]() | |
bool | pruneDCM (const PERM &t, unsigned int backtrackLevel, BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL) |
try to prune with advanced double coset minimality | |
bool | checkLeaf (unsigned int level) |
true iff level is a leaf level | |
unsigned int | processLeaf (const PERM &t, unsigned int level, unsigned int backtrackLevel, unsigned int completed, BSGS< PERM, TRANSRET > &groupK, BSGS< PERM, TRANSRET > &groupL) |
processes a leaf and adds corresponding element to the generator set of K | |
void | setupEmptySubgroup (BSGS< PERM, TRANSRET > &group) const |
sets up a BSGS structure for an empty group with base subgroupBase() | |
![]() | |
BSGSIN | m_bsgs |
main BSGS to search in | |
BSGSIN * | m_bsgs2 |
second BSGS of a group the sough elements have to member of | |
boost::scoped_ptr< SubgroupPredicate< PERM > > | m_pred |
predicate that matches sought elements | |
std::vector< unsigned long > | m_order |
base point order | |
boost::scoped_ptr< BaseSorterByReference > | m_sorter |
a sorter with respect to m_order | |
ConjugatingBaseChange< PERM, TRANS, RandomBaseTranspose< PERM, TRANS > > | m_baseChange |
base change algorithm | |
const unsigned int | m_pruningLevelDCM |
leves i with 0 <= i < m_pruningLevelDCM are prunged by advanced double coset minimality | |
bool | m_limitInitialized |
true iff other m_limit variables have been initialized | |
unsigned int | m_limitBase |
number of base points that correspond to maximal backtrack level m_limitLevel | |
unsigned int | m_limitLevel |
maximal backtrack level | |
const bool | m_stopAfterFirstElement |
true iff the search can be stopped after the first element found with the desired property | |
PERM::ptr | m_lastElement |
last element found with desired property; only used if m_stopAfterFirstElement is true | |
coset representative search for a lex-smaller set images
tries to find a such that
permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET >::LexSmallerImageSearch | ( | const BSGSIN & | bsgs, |
unsigned int | pruningLevelDCM | ||
) |
constructor
bsgs | BSGS of group |
pruningLevelDCM | level up to which expensive double coset minimality pruning is performed; zero to disable |
void permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET >::construct | ( | InputIteratorZ | zerosBegin, |
InputIteratorZ | zerosEnd, | ||
InputIteratorO | onesBegin, | ||
InputIteratorO | onesEnd | ||
) |
initializes search
begin | iterator(unsigned long) begin of the set ![]() |
end | iterator(unsigned long) end of the set ![]() |
beginImg | iterator(unsigned long) begin of the set ![]() |
endImg | iterator(unsigned long) end of the set ![]() |