33 #ifndef LEXSMALLERIMAGE_PREDICATE_H_ 34 #define LEXSMALLERIMAGE_PREDICATE_H_ 36 #include <permlib/predicate/subgroup_predicate.h> 39 #include <boost/foreach.hpp> 40 #include <boost/dynamic_bitset.hpp> 59 template<
class ForwardIterator>
60 LexSmallerImagePredicate(
unsigned int n, ForwardIterator zerosBegin, ForwardIterator zerosEnd, ForwardIterator onesBegin, ForwardIterator onesEnd);
63 virtual bool childRestriction(
const PERM &h,
unsigned int i,
unsigned long beta_i)
const;
64 virtual unsigned int limit()
const;
66 boost::dynamic_bitset<> m_zeros;
67 boost::dynamic_bitset<> m_ones;
68 unsigned long m_fixed;
76 template<
class ForwardIterator>
78 : m_zeros(n), m_ones(n), m_fixed(0)
80 while (zerosBegin != zerosEnd) {
81 m_zeros.set(*zerosBegin++, 1);
84 while (onesBegin != onesEnd) {
85 m_ones.set(*onesBegin++, 1);
93 for (
unsigned int i = 0; i < p.size(); ++i) {
94 const dom_int pi = p / i;
97 if (m_ones[i] && m_zeros[pi]) {
98 PERMLIB_DEBUG( std::cout << i <<
" , " << pi <<
" !0 -> 0 TRUE" << std::endl; )
101 if (m_zeros[i] && !m_zeros[pi]) {
102 PERMLIB_DEBUG( std::cout << i <<
" , " << pi <<
" 0 -> !0 FALSE" << std::endl; )
109 template <
class PERM>
115 PERMLIB_DEBUG( std::cout << h <<
" is already the desired element; TRUE" << std::endl; )
118 if (m_zeros[beta_i] && !m_zeros[h / beta_i]) {
119 PERMLIB_DEBUG( std::cout << (h / beta_i) <<
" mapping zero " << beta_i <<
" to non-zero; FALSE" << std::endl; )
125 template <
class PERM>
132 #endif // -- LEXSMALLERIMAGE_PREDICATE_H_ LexSmallerImagePredicate(unsigned int n, ForwardIterator zerosBegin, ForwardIterator zerosEnd, ForwardIterator onesBegin, ForwardIterator onesEnd)
constructor
Definition: lex_smaller_image_predicate.h:77
coset-type predicate for group elements that map one set of zeros and ones to a lex-smaller set (w...
Definition: lex_smaller_image_predicate.h:49
virtual unsigned int limit() const
limit of recursion depth in backtrack search
Definition: lex_smaller_image_predicate.h:126
virtual bool operator()(const PERM &p) const
true iff group element fulfills predicate
Definition: lex_smaller_image_predicate.h:92
virtual bool childRestriction(const PERM &h, unsigned int i, unsigned long beta_i) const
checks if a given group element should not be followed in backtrack search
Definition: lex_smaller_image_predicate.h:110
abstract base class for subgroup (and coset) predicates
Definition: subgroup_predicate.h:45
Definition: abstract_bsgs.h:49