Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	Safe-Inferred
Language	GHC2021

HGeometry.Permutation

Description

Data type for representing a non-empty Permutation

Synopsis

data Permutation a = Permutation (NonEmptyVector (Orbit a)) (Vector (Int, Int))
orbits :: Lens (Permutation a) (Permutation b) (NonEmptyVector (Orbit a)) (NonEmptyVector (Orbit b))
indices :: (Indexable i p, Applicative f) => (i -> Bool) -> Optical' p (Indexed i) f a a
type Orbit a = NonEmptyVector a
elems :: Permutation a -> NonEmptyVector a
size :: Permutation a -> Int
cycleOf :: Enum a => Permutation a -> a -> Orbit a
next :: NonEmptyVector a -> Int -> a
previous :: NonEmptyVector a -> Int -> a
lookupIdx :: Enum a => Permutation a -> a -> (Int, Int)
apply :: Enum a => Permutation a -> a -> a
orbitFrom :: Eq a => a -> (a -> a) -> NonEmpty a
cycleRep :: (Enum a, Eq a) => NonEmptyVector a -> (a -> a) -> Permutation a
toCycleRep :: Enum a => Int -> NonEmpty (NonEmpty a) -> Permutation a

Documentation

data Permutation a Source #

Cyclic representation of a non-empty permutation.

Constructors

Permutation (NonEmptyVector (Orbit a)) (Vector (Int, Int))

Instances

Instances details

Foldable Permutation Source #
Instance details Defined in HGeometry.Permutation Methods fold :: Monoid m => Permutation m -> m # foldMap :: Monoid m => (a -> m) -> Permutation a -> 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 #
Traversable Permutation Source #
Instance details Defined in HGeometry.Permutation Methods traverse :: 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) #
Functor Permutation Source #
Instance details Defined in HGeometry.Permutation Methods fmap :: (a -> b) -> Permutation a -> Permutation b # (<$) :: a -> Permutation b -> Permutation a #
Generic (Permutation a) Source #
Instance details Defined in HGeometry.Permutation Associated Types type Rep (Permutation a) :: Type -> Type # Methods from :: Permutation a -> Rep (Permutation a) x # to :: Rep (Permutation a) x -> Permutation a #
Show a => Show (Permutation a) Source #
Instance details Defined in HGeometry.Permutation Methods showsPrec :: Int -> Permutation a -> ShowS # show :: Permutation a -> String # showList :: [Permutation a] -> ShowS #
NFData a => NFData (Permutation a) Source #
Instance details Defined in HGeometry.Permutation Methods rnf :: Permutation a -> () #
Eq a => Eq (Permutation a) Source #
Instance details Defined in HGeometry.Permutation Methods (==) :: Permutation a -> Permutation a -> Bool # (/=) :: Permutation a -> Permutation a -> Bool #
type Rep (Permutation a) Source #
Instance details Defined in HGeometry.Permutation type Rep (Permutation a) = D1 ('MetaData "Permutation" "HGeometry.Permutation" "hgeometry-combinatorial-1.0.0.0-inplace" 'False) (C1 ('MetaCons "Permutation" 'PrefixI 'True) (S1 ('MetaSel ('Just "_orbits") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (NonEmptyVector (Orbit a))) :*: S1 ('MetaSel ('Just "_indexes") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Vector (Int, Int)))))

orbits :: Lens (Permutation a) (Permutation b) (NonEmptyVector (Orbit a)) (NonEmptyVector (Orbit b)) Source #

Lens to access the orbits of the permutation

indices :: (Indexable i p, Applicative f) => (i -> Bool) -> Optical' p (Indexed i) f a a Source #

This allows you to filter an IndexedFold, IndexedGetter, IndexedTraversal or IndexedLens based on a predicate on the indices.

>>> ["hello","the","world","!!!"]^..traversed.indices even
["hello","world"]

>>> over (traversed.indices (>0)) Prelude.reverse $ ["He","was","stressed","o_O"]
["He","saw","desserts","O_o"]

type Orbit a = NonEmptyVector a Source #

Orbits (Cycles) are represented by vectors

elems :: Permutation a -> NonEmptyVector a Source #

Get the elements of the permutation

size :: Permutation a -> Int Source #

Get the size of a permutation

running time: $O(1)$

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

The cycle containing a given item

next :: NonEmptyVector a -> Int -> a Source #

Next item in a cyclic permutation

previous :: NonEmptyVector 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) -> NonEmpty a Source #

Find the cycle in the permutation starting at element s

cycleRep :: (Enum a, Eq a) => NonEmptyVector 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 -> NonEmpty (NonEmpty a) -> Permutation a Source #

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