perfect-vector-shuffle-0.1.1: Library for performing vector shuffles

Safe HaskellNone
LanguageHaskell2010

Immutable.Shuffle

Description

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

Synopsis

Documentation

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

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) Source #

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) Source #

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) Source #

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

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

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) Source #

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) Source #

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) Source #

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.