permlib  0.2.9
Library for permutation computations
Classes | Public Member Functions | Static Public Member Functions | List of all members
permlib::OrbitLexMinSearch< BSGSIN > Class Template Reference

algorithm to find the lexicographically minimal set in an orbit More...

#include <orbit_lex_min_search.h>

Public Member Functions

 OrbitLexMinSearch (const BSGSIN &bsgs, bool abortSearchIfSmallerFound=false)
 constructor More...
 
dset lexMin (const dset &element, const BSGSIN *stabilizer=NULL)
 searches the lexicographically minimal element of an orbit More...
 

Static Public Member Functions

static bool isLexSmaller (const dset &a, const dset &b)
 compares two sets given as dsets lexicographically More...
 

Detailed Description

template<class BSGSIN>
class permlib::OrbitLexMinSearch< BSGSIN >

algorithm to find the lexicographically minimal set in an orbit

implements the algorithm `‘Finding the Smallest Image of a Set’' by Steve Linton, 2004

Constructor & Destructor Documentation

◆ OrbitLexMinSearch()

template<class BSGSIN>
permlib::OrbitLexMinSearch< BSGSIN >::OrbitLexMinSearch ( const BSGSIN &  bsgs,
bool  abortSearchIfSmallerFound = false 
)
inline

constructor

Parameters
bsgsthe group to build the orbit from
abortSearchIfSmallerFoundIf true, the lexMin search is aborted if a lex-smaller element is found. In this case the search does not necessarily find the minimal element.

Member Function Documentation

◆ isLexSmaller()

template<class BSGSIN >
bool permlib::OrbitLexMinSearch< BSGSIN >::isLexSmaller ( const dset &  a,
const dset &  b 
)
inlinestatic

compares two sets given as dsets lexicographically

This is different to a < b as dynamic_bitsets because we are interested in the the representation of the bitsets as sets.

◆ lexMin()

template<class BSGSIN >
dset permlib::OrbitLexMinSearch< BSGSIN >::lexMin ( const dset &  element,
const BSGSIN *  stabilizer = NULL 
)
inline

searches the lexicographically minimal element of an orbit

Parameters
elementone element of the orbit
stabilizersetwise stabilizer of given set in the group; if present may speed up computations; parameter is currently ignored
Returns
lexicographically smallest orbit element

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