Mutable.Shuffle

This module provides functions to perform shuffles on mutable vectors. The shuffling is uniform amongst all permuations and uses the minimal number of transpositions.

Documentation

shuffle :: forall m a g. (PrimMonad m, RandomGen g) => MVector (PrimState m) a -> g -> m g

Perform a shuffle on a mutable vector with a given random generator, returning a new random generator.

This uses the Fisher--Yates--Knuth algorithm

shuffleM :: forall m a. (PrimMonad m, MonadRandom m) => MVector (PrimState m) a -> m ()

Perform a shuffle on a mutable vector in a monad which has a source of randomness.

This uses the Fisher--Yates--Knuth algorithm

shuffleK :: forall m a. (PrimMonad m, MonadRandom m) => Int -> MVector (PrimState m) a -> m ()

Shuffle the first k elements of a vector.

maximalCycle :: forall m a g. (PrimMonad m, RandomGen g) => MVector (PrimState m) a -> g -> m g

Perform a shuffle on a mutable vector wherein the shuffled indices form a maximal cycle.

This uses the Sattolo algorithm.

maximalCycleM :: forall m a. (PrimMonad m, MonadRandom m) => MVector (PrimState m) a -> m ()

Perform a shuffle on a mutable vector wherein the shuffled indices form a maximal cycle in a monad with a source of randomness.

This uses the Sattolo algorithm.

derangement :: forall m a g. (PrimMonad m, RandomGen g, Eq a) => MVector (PrimState m) a -> g -> m g

Perform a derangement on a mutable vector with a given random generator, returning a new random generator.

Note: It is assumed the input vector consists of distinct values.

This uses the "early refusal" algorithm.

derangementM :: forall m a. (PrimMonad m, MonadRandom m, Eq a) => MVector (PrimState m) a -> m ()

Perform a derangement on a mutable vector in a monad which has a source of randomness.

Note: It is assumed the input vector consists of distinct values.

This uses the "early refusal" algorithm