List.hs

module RandomCycle.List
  ( -- * Partitions
    uniformPartition,
    uniformPartitionThin,
    partitionLengths,
    partitionFromBits,

    -- * Cycles
    uniformCycle,
    uniformCyclePartition,
    uniformCyclePartitionThin,
  )
where

import Control.Monad.Primitive (PrimMonad)
import qualified Data.Vector as V
import RandomCycle.List.Partition
import qualified RandomCycle.Vector as RV
import System.Random.Stateful (StatefulGen)

-- | Implements [Sattolo's algorithm](https://algo.inria.fr/seminars/summary/Wilson2004b.pdf)
-- to sample a full cycle permutation uniformly over /(n-1)!/ possibilities in /O(n)/ time.
-- The list implementation is a convenience wrapper around 'RandomCycle.Vector.uniformCycle'.
uniformCycle :: (PrimMonad m, StatefulGen g m) => Int -> g -> m [(Int, Int)]
uniformCycle n g = V.toList <$> RV.uniformCycle n g

-- | Sample a cycle graph partition of @[0.. n-1]@,
-- uniformly over the /n!/ possibilities. The list implementation
-- is a convenience wrapper around 'RandomCycle.Vector.uniformCyclePartition'.
uniformCyclePartition :: (PrimMonad m, StatefulGen g m) => Int -> g -> m [(Int, Int)]
uniformCyclePartition n g = V.toList <$> RV.uniformCyclePartition n g

-- | Sample a cycle graph partition of @[0.. n-1]@,
-- uniformly over the set satisfying the conditions.
-- The list implementation is a convenience wrapper around
-- 'RandomCycle.Vector.uniformCyclePartitionThin'.
uniformCyclePartitionThin ::
  (PrimMonad m, StatefulGen g m) =>
  -- | maximum number of draws to attempt
  Int ->
  -- | edge-wise predicate, which all edges in the result must satisfy
  ((Int, Int) -> Bool) ->
  -- | number of vertices, which will be labeled @[0..n-1]@
  Int ->
  g ->
  m (Maybe [(Int, Int)])
uniformCyclePartitionThin maxit r n g =
  fmap V.toList
    <$> RV.uniformCyclePartitionThin maxit r n g