Safe Haskell | None |
---|---|

Language | Haskell2010 |

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

- shuffle :: forall a g. RandomGen g => Vector a -> g -> (Vector a, g)
- shuffleM :: forall m a. (MonadRandom m, PrimMonad m) => Vector a -> m (Vector a)
- shuffleK :: forall m a. (MonadRandom m, PrimMonad m) => Int -> Vector a -> m (Vector a)
- sampleWithoutReplacement :: forall m a. (MonadRandom m, PrimMonad m) => Int -> Vector a -> m (Vector a)
- maximalCycle :: forall a g. RandomGen g => Vector a -> g -> (Vector a, g)
- maximalCycleM :: forall m a. (MonadRandom m, PrimMonad m) => Vector a -> m (Vector a)
- derangement :: forall a g. (Eq a, RandomGen g) => Vector a -> g -> (Vector a, g)
- derangementM :: forall m a. (Eq a, MonadRandom m, PrimMonad m) => Vector a -> m (Vector a)

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