Safe Haskell	None
Language	GHC2021

AtCoder.Extra.Semigroup.Permutation

Contents

Permutation
Constructors
Actions
Metadata

Description

A permutation represented by a vector, mainly for binary exponentiation.

The permutation is a left semigroup action: \(p_2 (p_1 x) = (p_2 \circ p_1) x\).

Example

Expand

>>> 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 1
2

>>> Permutation.act (perm <> perm) 1
3

>>> Permutation.act (stimes 3 perm) 1
0

Since: 1.1.0.0

Synopsis

newtype Permutation = Permutation {
- unPermutation :: Vector Int
}
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: \(p_2 (p_1 x) = (p_2 \circ p_1) x\).

Since: 1.1.0.0

Constructors

Permutation
Fields unPermutation :: Vector Int Since: 1.1.0.0

Instances

Instances details

Semigroup Permutation Source #	Since: 1.1.0.0
Instance details 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
Instance details 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
Instance details Defined in AtCoder.Extra.Semigroup.Permutation Methods (==) :: Permutation -> Permutation -> Bool # (/=) :: Permutation -> Permutation -> Bool #

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