AtCoder.Extra.Semigroup.Permutation

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

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

Permutation

newtype Permutation

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

Instances

Semigroup Permutation

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

Since: 1.1.0.0

Defined in AtCoder.Extra.Semigroup.Permutation

Methods

showsPrec :: Int -> Permutation -> ShowS

show :: Permutation -> String

showList :: [Permutation] -> ShowS

Eq Permutation

Since: 1.1.0.0

Defined in AtCoder.Extra.Semigroup.Permutation

Methods

(==) :: Permutation -> Permutation -> Bool

(/=) :: Permutation -> Permutation -> Bool

Constructors

new :: HasCallStack => Vector Int -> Permutation

\(O(1)\) Creates a Permutation, performing boundary check on input vector.

Since: 1.1.0.0

unsafeNew :: HasCallStack => Vector Int -> Permutation

\(O(1)\) Creates a Permutation, without performing boundary check on input vector.

Since: 1.1.0.0

ident :: Int -> Permutation

\(O(1)\) Creates an identity Permutation of length \(n\).

Since: 1.1.0.0

zero :: Int -> Permutation

\(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

\(O(1)\) Maps an index.

Since: 1.1.0.0

Metadata

length :: HasCallStack => Permutation -> Int

\(O(1)\) Returns the length of the internal vector.

Since: 1.1.0.0