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). KnownNat n => 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 #	Extends the `Monoid` instance using `invert`
Instance details Defined in Advent.Permutation Methods inverse :: Permutation n -> Permutation n Source #
KnownNat n => Monoid (Permutation n) Source #	Extend the `Semigroup` instance with an identity permutation as `mempty`. `>>>` `mempty :: Permutation 6`[0,1,2,3,4,5]
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`. `>>>` `swap 1 2 <> swap 3 4 <> swap 4 5 :: Permutation 6`[0,2,1,4,5,3]
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 #
KnownNat n => Read (Permutation n) Source #	Parse a permutation as a list literal.
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 #	Render a permutation as a list literal. `>>>` `show (mempty :: Permutation 4)`"[0,1,2,3]"
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 #

Produce a list mapping list elements from their indexes to their output elements.

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.

>>> swap 2 3 :: Permutation 5
[0,1,3,2,4]

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

Permutation generated by rotating all the elements to the right.

>>> rotateRight 2 :: Permutation 5
[3,4,0,1,2]

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

Permutation generated by rotating all the elements to the left.

>>> rotateLeft 2 :: Permutation 5
[2,3,4,0,1]

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

Permutation generated by inverting another permutation.

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

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

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

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

>>> isValid (mempty :: Permutation 5)
True

>>> isValid (mkPermutation (const 0) :: Permutation 5)
False

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

Size of the list of elements permuted.

>>> size (mempty :: Permutation 5)
5

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

Permutation generated by reversing the order of the elements.

>>> backwards :: Permutation 4
[3,2,1,0]

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