| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.Semigroup.Permutation
Description
A permutation represented by a vector, mainly for binary exponentiation.
The permutation is a left semigroup action: p2(p1x)=(p2∘p1)x.
Example
>>>import AtCoder.Extra.Semigroup.Permutation qualified as Permutation>>>import Data.Semigroup (Semigroup (stimes))>>>import Data.Vector.Unboxed qualified as VU>>>let perm = Permutation.new $ VU.fromList [1, 2, 3, 0]>>>Permutation.act perm 12
>>>Permutation.act (perm <> perm) 13
>>>Permutation.act (stimes 3 perm) 10
Since: 1.1.0.0
Synopsis
- newtype Permutation = Permutation {}
- new :: HasCallStack => Vector Int -> Permutation
- unsafeNew :: HasCallStack => Vector Int -> Permutation
- ident :: Int -> Permutation
- zero :: Int -> Permutation
- act :: HasCallStack => Permutation -> Int -> Int
- length :: HasCallStack => Permutation -> Int
Permutation
newtype Permutation Source #
A permutation represented by a vector, mainly for binary exponentiation.
The permutation is a left semigroup action: p2(p1x)=(p2∘p1)x.
Since: 1.1.0.0
Constructors
| Permutation | |
Fields | |
Instances
| Semigroup Permutation Source # | Since: 1.1.0.0 |
Defined in AtCoder.Extra.Semigroup.Permutation Methods (<>) :: Permutation -> Permutation -> Permutation # sconcat :: NonEmpty Permutation -> Permutation # stimes :: Integral b => b -> Permutation -> Permutation # | |
| Show Permutation Source # | Since: 1.1.0.0 |
Defined in AtCoder.Extra.Semigroup.Permutation Methods showsPrec :: Int -> Permutation -> ShowS # show :: Permutation -> String # showList :: [Permutation] -> ShowS # | |
| Eq Permutation Source # | Since: 1.1.0.0 |
Defined in AtCoder.Extra.Semigroup.Permutation | |
Constructors
new :: HasCallStack => Vector Int -> Permutation Source #
O(1) Creates a Permutation, performing boundary check on input vector.
Since: 1.1.0.0
unsafeNew :: HasCallStack => Vector Int -> Permutation Source #
O(1) Creates a Permutation, without performing boundary check on input vector.
Since: 1.1.0.0
ident :: Int -> Permutation Source #
O(1) Creates an identity Permutation of length n.
Since: 1.1.0.0
zero :: Int -> Permutation Source #
O(1) Creates a zero Permutation of length n. It's similar to ident, but filled
with −1 and invalidates corresponding slots on composition.
Since: 1.1.0.0
Actions
act :: HasCallStack => Permutation -> Int -> Int Source #
O(1) Maps an index.
Since: 1.1.0.0
Metadata
length :: HasCallStack => Permutation -> Int Source #
O(1) Returns the length of the internal vector.
Since: 1.1.0.0