-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Uniform draws of partitions and cycle-partitions, with thinning.
--
-- A Haskell library for efficient uniform random sampling of cycle
-- partition graphs on sets of vertices, and partitions of lists or
-- vectors. Selection can be subject to conditions.
@package random-cycle
@version 0.1.2.0
module RandomCycle.Vector
-- | Draw a random partition of the input vector xs from the
-- uniform distribution on partitions. This proceeds by randomizing the
-- placement of each breakpoint, in other words by walking a random path
-- in a perfect binary tree. O(n) for a vector length n.
--
-- This function preserves the order of the input list.
uniformPartition :: (Vector v a, StatefulGen g m) => v a -> g -> m [v a]
-- | Partition a vector v according to groupings provided by the
-- bits bs. If the first set bit in bs is at a position
-- larger than the last index of v, this returns [v].
-- More generally, bits set at positions after the last index of
-- v do not contribute to the grouping. bs == 0 always
-- results in [v].
--
-- See partitionFromBits for other examples.
--
-- Examples
--
--
-- >>> import qualified Data.Vector as V
--
-- >>> partitionFromBits 5 (V.fromList [0..2::Int])
-- [[0],[1],[2]]
--
-- >>> partitionFromBits 13 (V.fromList [0..2::Int])
-- [[0],[1],[2]]
--
-- >>> partitionFromBits 4 (V.fromList [0..2::Int])
-- [[0,1],[2]]
--
-- >>> partitionFromBits 8 (V.fromList [0..2::Int])
-- [[0,1,2]]
--
partitionFromBits :: Vector v a => Natural -> v a -> [v a]
-- | Implements Sattolo's algorithm to sample a full cycle
-- permutation uniformly over (n-1)! possibilities in O(n)
-- time. The algorithm is nearly identical to the Fisher-Yates shuffle on
-- [0..n-1], and therefore this implementation is very similar
-- to that of uniformPermutation.
--
-- This will throw an exception with syntax analogous to
-- uniformPermutation if the provided size is negative.
--
-- Examples
--
--
-- >>> import System.Random.Stateful
--
-- >>> import RandomCycle.Vector
--
-- >>> runSTGen_ (mkStdGen 1901) $ uniformCycle 4
-- [(0,3),(1,0),(2,1),(3,2)]
--
uniformCycle :: (StatefulGen g m, PrimMonad m) => Int -> g -> m (Vector (Int, Int))
-- | Select a partition of [0..n-1] into disjoint cycle
-- graphs, uniformly over the n! possibilities. The sampler
-- relies on the fact that such partitions are isomorphic with the
-- permutations of [0..n-1] via the map sending a permutation
-- sigma to the edge set {(i, sigma(i))}_0^{n-1}.
--
-- Therefore, this function simply calls uniformPermutation and
-- tuples the result with its indices. The returned value is a vector of
-- edges. O(n), since uniformPermutation implements the
-- Fisher-Yates shuffle.
--
-- uniformPermutation uses in-place mutation, so this function
-- must be run in a PrimMonad context.
--
-- Examples
--
--
-- >>> import System.Random.Stateful
--
-- >>> import qualified RandomCycle.Vector as RV
--
-- >>> import Data.Vector (Vector)
--
-- >>> runSTGen_ (mkStdGen 1305) $ RV.uniformCyclePartition 4 :: Vector (Int, Int)
-- [(0,1),(1,3),(2,2),(3,0)]
--
uniformCyclePartition :: (StatefulGen g m, PrimMonad m) => Int -> g -> m (Vector (Int, Int))
-- | Uniform selection of a cycle partition graph of [0..n-1]
-- elements, conditional on an edge-wise predicate. See
-- uniformCyclePartition for details on the sampler.
--
-- O(n/p), where p is the probability that a uniformly
-- sampled cycle partition graph (over all n! possible) satisfies
-- the conditions. This can be highly non-linear since p in
-- general is a function of n.
--
-- Since this is a rejection sampling method, the user is asked to
-- provide a counter for the maximum number of sampling attempts in order
-- to guarantee termination in cases where the edge predicate has
-- probability of success close to zero.
--
-- Note this will return pure Nothing if given a number of
-- vertices that is non-positive, in the third argument, unlike
-- uniformCyclePartition which will throw an error.
--
-- Examples
--
--
-- >>> import System.Random.Stateful
--
-- >>> import qualified RandomCycle.Vector as RV
--
-- >>> import Data.Vector (Vector)
--
-- >>> -- No self-loops
--
-- >>> rule = uncurry (/=)
--
-- >>> n = 5
--
-- >>> maxit = n * 1000
--
-- >>> runSTGen_ (mkStdGen 3) $ RV.uniformCyclePartitionThin maxit rule n
-- Just [(0,2),(1,3),(2,0),(3,4),(4,1)]
--
uniformCyclePartitionThin :: (StatefulGen g m, PrimMonad m) => Int -> ((Int, Int) -> Bool) -> Int -> g -> m (Maybe (Vector (Int, Int)))
module RandomCycle.List
-- | Draw a random partition of the input list xs from the uniform
-- distribution on partitions. This proceeds by randomizing the placement
-- of each breakpoint, in other words by walking a random path in a
-- perfect binary tree. O(n) for a vector length n.
--
-- This function preserves the order of the input list.
--
-- Examples
--
--
-- >>> import System.Random.Stateful
--
-- >>> pureGen = mkStdGen 0
--
-- >>> runStateGen_ pureGen $ uniformPartition [1..5::Int]
-- [[1,2,3],[4],[5]]
--
-- >>> runStateGen_ pureGen $ uniformPartition ([] :: [Int])
-- []
--
uniformPartition :: StatefulGen g m => [a] -> g -> m [[a]]
-- | Generate a partition with a local condition r on each
-- partition element. Construction of a partition shortcircuits to
-- failure as soon as the local condition is false.
--
-- Since this is a rejection sampling method, the user is asked to
-- provide a counter for the maximum number of sampling attempts in order
-- to guarantee termination in cases where the edge predicate has
-- probability of success close to zero.
--
-- Run time on average is O(n/p) where p is the probability
-- all r yss == True for a uniformly generated partition
-- yss, assuming r has run time linear in the length of
-- its argument. This can be highly non-linear because p in
-- general is a function of n.
--
-- Some cases can perhaps be deceptively expensive: For example, the
-- condition r = ((>= 2) . length) leads to huge runtimes,
-- since the number of partitions with at least one element of length 1
-- is exponential in n.
--
-- Examples
--
--
-- >>> import System.Random.Stateful
--
-- >>> maxit = 1000
--
-- >>> pureGen = mkStdGen 0
--
-- >>> r = (>= 2) . length
--
-- >>> runStateGen_ pureGen $ uniformPartitionThin maxit r [1..5::Int]
-- Just [[1,2],[3, 4, 5]]
--
-- >>> runStateGen_ pureGen $ uniformPartitionThin maxit (const False) ([] :: [Int])
-- Just []
--
-- >>> runStateGen_ pureGen $ uniformPartitionThin maxit r [1::Int]
-- Nothing
--
uniformPartitionThin :: StatefulGen g m => Int -> ([a] -> Bool) -> [a] -> g -> m (Maybe [[a]])
-- | Primarily a testing utility, to compute directly the lengths of each
-- partition element for a list of size n, using
-- countTrailingZeros. Note this uses Word.
partitionLengths :: Word -> Int -> [Int]
-- | Utility to generate a list partition using the provided Natural
-- as grouping variable, viewed as Bits. The choice of grouping
-- variable is to improve performance since the number of partitions
-- grows exponentially in the input list length.
--
-- This can be used to generate a list of all possible partitions of the
-- input list as shown in the example. See partitionFromBits for
-- other examples.
--
--
-- >>> import GHC.Natural
--
-- >>> allPartitions n | n < 0 = []
--
-- >>> allPartitions n = map (`partitionFromBits` [0..n-1]) [0 .. 2^(n-1) - 1]
--
-- >>> allPartitions 4
-- [[[0,1,2,3]],[[0],[1,2,3]],[[0],[1],[2,3]],[[0,1],[2,3]],[[0,1],[2],[3]],[[0],[1],[2],[3
-- ]],[[0],[1,2],[3]],[[0,1,2],[3]]]
--
partitionFromBits :: Natural -> [a] -> [[a]]
-- | Implements Sattolo's algorithm to sample a full cycle
-- permutation uniformly over (n-1)! possibilities in O(n)
-- time. The list implementation is a convenience wrapper around
-- uniformCycle.
uniformCycle :: (PrimMonad m, StatefulGen g m) => Int -> g -> m [(Int, Int)]
-- | Sample a cycle graph partition of [0.. n-1], uniformly over
-- the n! possibilities. The list implementation is a convenience
-- wrapper around uniformCyclePartition.
uniformCyclePartition :: (PrimMonad m, StatefulGen g m) => Int -> g -> m [(Int, Int)]
-- | Sample a cycle graph partition of [0.. n-1], uniformly over
-- the set satisfying the conditions. The list implementation is a
-- convenience wrapper around uniformCyclePartitionThin.
uniformCyclePartitionThin :: (PrimMonad m, StatefulGen g m) => Int -> ((Int, Int) -> Bool) -> Int -> g -> m (Maybe [(Int, Int)])