Immutable.Shuffle

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

Documentation

shuffle :: forall a g. RandomGen g => Vector a -> g -> (Vector a, g)

Perform a shuffle on an immutable vector with a given random generator returning a shuffled vector and a new generator.

This uses the Fisher--Yates--Knuth algorithm.

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

Perform a shuffle on an input immutable vector in a monad which has a source of randomness.

This uses the Fisher--Yates--Knuth algorithm.

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

Perform a shuffle on the first k elements of a vector in a monad which has a source of randomness.

sampleWithoutReplacement :: forall m a. (MonadRandom m, PrimMonad m) => Int -> Vector a -> m (Vector a)

Get a random sample of k elements without replacement from a vector.

maximalCycle :: forall a g. RandomGen g => Vector a -> g -> (Vector a, g)

Perform an in-place shuffle on an immutable vector wherein the shuffled indices form a maximal cycle.

This uses the Sattolo algorithm.

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

Perform an in-place shuffle on an immutable vector wherein the shuffled indices form a maximal cycle in a monad with a source of randomness.

This uses the Sattolo algorithm.

derangement :: forall a g. (Eq a, RandomGen g) => Vector a -> g -> (Vector a, g)

Perform an in-place derangement on an immutable 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. (Eq a, MonadRandom m, PrimMonad m) => Vector a -> m (Vector a)

Perform an in-place derangement on an immutable 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.