permlib  0.2.9
Library for permutation computations
Public Types | Public Member Functions | List of all members
permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET > Class Template Reference

coset representative search for a lex-smaller set images More...

#include <lex_smaller_image_search.h>

Inheritance diagram for permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET >:
permlib::classic::BacktrackSearch< BSGSIN, TRANSRET > permlib::BaseSearch< BSGSIN, TRANSRET >

Public Types

typedef BacktrackSearch< BSGSIN, TRANSRET >::PERM PERM
 
- Public Types inherited from permlib::classic::BacktrackSearch< BSGSIN, TRANSRET >
typedef BaseSearch< BSGSIN, TRANSRET >::PERM PERM
 
typedef BaseSearch< BSGSIN, TRANSRET >::TRANS TRANS
 
- Public Types inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
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...
 
- Public Member Functions inherited from permlib::classic::BacktrackSearch< BSGSIN, TRANSRET >
 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...
 
- Public Member Functions inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
 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

- Public Attributes inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
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
 
- Protected Member Functions inherited from permlib::classic::BacktrackSearch< BSGSIN, TRANSRET >
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
 
- Protected Member Functions inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
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()
 
- Protected Attributes inherited from permlib::BaseSearch< BSGSIN, TRANSRET >
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< BaseSorterByReferencem_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
 

Detailed Description

template<class BSGSIN, class TRANSRET>
class permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET >

coset representative search for a lex-smaller set images

tries to find a $g$ such that $val(\Delta^g) <_{lex} val(\Delta)$

Constructor & Destructor Documentation

◆ LexSmallerImageSearch()

template<class BSGSIN , class TRANSRET >
permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET >::LexSmallerImageSearch ( const BSGSIN &  bsgs,
unsigned int  pruningLevelDCM 
)

constructor

Parameters
bsgsBSGS of group
pruningLevelDCMlevel up to which expensive double coset minimality pruning is performed; zero to disable

Member Function Documentation

◆ construct()

template<class BSGSIN , class TRANSRET >
template<class InputIteratorZ , class InputIteratorO >
void permlib::classic::LexSmallerImageSearch< BSGSIN, TRANSRET >::construct ( InputIteratorZ  zerosBegin,
InputIteratorZ  zerosEnd,
InputIteratorO  onesBegin,
InputIteratorO  onesEnd 
)

initializes search

Parameters
beginiterator(unsigned long) begin of the set $\Delta$
enditerator(unsigned long) end of the set $\Delta$
beginImgiterator(unsigned long) begin of the set $\Gamma$
endImgiterator(unsigned long) end of the set $\Gamma$

The documentation for this class was generated from the following file: