Copyright	(c) Eric Mertens 2017
License	ISC
Maintainer	emertens@gmail.com
Safe Haskell	None
Language	Haskell2010

Advent.Permutation

Description

Common permutations of a finite collection of elements and operations on them.

Synopsis

data Permutation (n :: Nat)
runPermutation :: forall a (n :: Nat). (Int -> a) -> Permutation n -> [a]
mkPermutation :: forall (n :: Nat). KnownNat n => (Int -> Int) -> Permutation n
swap :: forall (n :: Nat). KnownNat n => Int -> Int -> Permutation n
rotateRight :: forall (n :: Nat). KnownNat n => Int -> Permutation n
rotateLeft :: forall (n :: Nat). KnownNat n => Int -> Permutation n
invert :: forall (n :: Nat). Permutation n -> Permutation n
isValid :: forall (n :: Nat). Permutation n -> Bool
size :: forall (n :: Nat). Permutation n -> Int
backwards :: forall (n :: Nat). KnownNat n => Permutation n
cycles :: forall (n :: Nat). Permutation n -> [[Int]]
order :: forall (n :: Nat). Permutation n -> Int

Documentation

data Permutation (n :: Nat) Source #

Permutations of n elements

Instances

Instances details

KnownNat n => Group (Permutation n) Source #
Instance details Defined in Advent.Permutation Methods inverse :: Permutation n -> Permutation n Source #
KnownNat n => Monoid (Permutation n) Source #
Instance details Defined in Advent.Permutation Methods mempty :: Permutation n # mappend :: Permutation n -> Permutation n -> Permutation n # mconcat :: [Permutation n] -> Permutation n #
Semigroup (Permutation n) Source #	`a <> b` is the permutation that first permutes with `a` and then with `b`.
Instance details Defined in Advent.Permutation Methods (<>) :: Permutation n -> Permutation n -> Permutation n # sconcat :: NonEmpty (Permutation n) -> Permutation n # stimes :: Integral b => b -> Permutation n -> Permutation n #
Read (Permutation n) Source #
Instance details Defined in Advent.Permutation Methods readsPrec :: Int -> ReadS (Permutation n) # readList :: ReadS [Permutation n] # readPrec :: ReadPrec (Permutation n) # readListPrec :: ReadPrec [Permutation n] #
Show (Permutation n) Source #
Instance details Defined in Advent.Permutation Methods showsPrec :: Int -> Permutation n -> ShowS # show :: Permutation n -> String # showList :: [Permutation n] -> ShowS #
Eq (Permutation n) Source #
Instance details Defined in Advent.Permutation Methods (==) :: Permutation n -> Permutation n -> Bool # (/=) :: Permutation n -> Permutation n -> Bool #
Ord (Permutation n) Source #
Instance details Defined in Advent.Permutation Methods compare :: Permutation n -> Permutation n -> Ordering # (<) :: Permutation n -> Permutation n -> Bool # (<=) :: Permutation n -> Permutation n -> Bool # (>) :: Permutation n -> Permutation n -> Bool # (>=) :: Permutation n -> Permutation n -> Bool # max :: Permutation n -> Permutation n -> Permutation n # min :: Permutation n -> Permutation n -> Permutation n #

runPermutation :: forall a (n :: Nat). (Int -> a) -> Permutation n -> [a] Source #

mkPermutation :: forall (n :: Nat). KnownNat n => (Int -> Int) -> Permutation n Source #

Given a function mapping incoming indices to outgoing ones, construct a new permutation value.

swap :: forall (n :: Nat). KnownNat n => Int -> Int -> Permutation n Source #

Permutation generated by swapping the elements at a pair of indices.

rotateRight :: forall (n :: Nat). KnownNat n => Int -> Permutation n Source #

Permutation generated by rotating all the elements to the right.

rotateLeft :: forall (n :: Nat). KnownNat n => Int -> Permutation n Source #

Permutation generated by rotating all the elements to the left.

invert :: forall (n :: Nat). Permutation n -> Permutation n Source #

Permutation generated by inverting another permutation.

isValid :: forall (n :: Nat). Permutation n -> Bool Source #

Validate a permutation. A valid permutation will map each element in the input to a unique element in the output.

size :: forall (n :: Nat). Permutation n -> Int Source #

Size of the list of elements permuted.

backwards :: forall (n :: Nat). KnownNat n => Permutation n Source #

Permutation generated by reversing the order of the elements.

cycles :: forall (n :: Nat). Permutation n -> [[Int]] Source #

Compute the disjoint cycles of the permutation.

>>> cycles (swap 1 2 <> swap 3 4 <> swap 4 5 :: Permutation 6)
[[0],[1,2],[3,4,5]]

order :: forall (n :: Nat). Permutation n -> Int Source #

Compute the order of a permutation.

>>> order (swap 1 2 <> swap 3 4 <> swap 4 5 :: Permutation 6)
6