hgeometry-combinatorial-0.9.0.0: Data structures, and Data types.

Data.Permutation

Description

Data type for representing a Permutation

Synopsis

# Documentation

type Orbit a = Vector a Source #

Orbits (Cycles) are represented by vectors

data Permutation a Source #

Cyclic representation of a permutation.

Constructors

 Permutation Fields_orbits :: Vector (Orbit a) _indexes :: Vector (Int, Int)idxes (fromEnum a) = (i,j) implies that a is the j^th item in the i^th orbit
Instances
 Source # Instance detailsDefined in Data.Permutation Methodsfmap :: (a -> b) -> Permutation a -> Permutation b #(<\$) :: a -> Permutation b -> Permutation a # Source # Instance detailsDefined in Data.Permutation Methodsfold :: Monoid m => Permutation m -> m #foldMap :: Monoid m => (a -> m) -> Permutation a -> m #foldr :: (a -> b -> b) -> b -> Permutation a -> b #foldr' :: (a -> b -> b) -> b -> Permutation a -> b #foldl :: (b -> a -> b) -> b -> Permutation a -> b #foldl' :: (b -> a -> b) -> b -> Permutation a -> b #foldr1 :: (a -> a -> a) -> Permutation a -> a #foldl1 :: (a -> a -> a) -> Permutation a -> a #toList :: Permutation a -> [a] #null :: Permutation a -> Bool #length :: Permutation a -> Int #elem :: Eq a => a -> Permutation a -> Bool #maximum :: Ord a => Permutation a -> a #minimum :: Ord a => Permutation a -> a #sum :: Num a => Permutation a -> a #product :: Num a => Permutation a -> a # Source # Instance detailsDefined in Data.Permutation Methodstraverse :: Applicative f => (a -> f b) -> Permutation a -> f (Permutation b) #sequenceA :: Applicative f => Permutation (f a) -> f (Permutation a) #mapM :: Monad m => (a -> m b) -> Permutation a -> m (Permutation b) #sequence :: Monad m => Permutation (m a) -> m (Permutation a) # Eq a => Eq (Permutation a) Source # Instance detailsDefined in Data.Permutation Methods(==) :: Permutation a -> Permutation a -> Bool #(/=) :: Permutation a -> Permutation a -> Bool # Show a => Show (Permutation a) Source # Instance detailsDefined in Data.Permutation MethodsshowsPrec :: Int -> Permutation a -> ShowS #show :: Permutation a -> String #showList :: [Permutation a] -> ShowS # Source # Instance detailsDefined in Data.Permutation Associated Typestype Rep (Permutation a) :: Type -> Type # Methodsfrom :: Permutation a -> Rep (Permutation a) x #to :: Rep (Permutation a) x -> Permutation a # NFData a => NFData (Permutation a) Source # Instance detailsDefined in Data.Permutation Methodsrnf :: Permutation a -> () # type Rep (Permutation a) Source # Instance detailsDefined in Data.Permutation type Rep (Permutation a) = D1 (MetaData "Permutation" "Data.Permutation" "hgeometry-combinatorial-0.9.0.0-6qy5VaQ7muxJuEfibyCL9S" False) (C1 (MetaCons "Permutation" PrefixI True) (S1 (MetaSel (Just "_orbits") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Vector (Orbit a))) :*: S1 (MetaSel (Just "_indexes") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Vector (Int, Int)))))

orbits :: forall a a. Lens (Permutation a) (Permutation a) (Vector (Orbit a)) (Vector (Orbit a)) Source #

indexes :: forall a. Lens' (Permutation a) (Vector (Int, Int)) Source #

cycleOf :: Enum a => Permutation a -> a -> Orbit a Source #

The cycle containing a given item

next :: Vector v a => v a -> Int -> a Source #

Next item in a cyclic permutation

previous :: Vector v a => v a -> Int -> a Source #

Previous item in a cyclic permutation

lookupIdx :: Enum a => Permutation a -> a -> (Int, Int) Source #

Lookup the indices of an element, i.e. in which orbit the item is, and the index within the orbit.

runnign time: $$O(1)$$

apply :: Enum a => Permutation a -> a -> a Source #

Apply the permutation, i.e. consider the permutation as a function.

orbitFrom :: Eq a => a -> (a -> a) -> [a] Source #

Find the cycle in the permutation starting at element s

cycleRep :: (Vector v a, Enum a, Eq a) => v a -> (a -> a) -> Permutation a Source #

Given a vector with items in the permutation, and a permutation (by its functional representation) construct the cyclic representation of the permutation.

toCycleRep :: Enum a => Int -> [[a]] -> Permutation a Source #

Given the size n, and a list of Cycles, turns the cycles into a cyclic representation of the Permutation.

genIndexes :: Enum a => Int -> [[a]] -> Vector (Int, Int) Source #