random-cycle 0.1.0.0 → 0.1.0.1

raw patch · 7 files changed

+66/−28 lines, 7 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• CHANGELOG.md +4/−0
• README.md +10/−7
• random-cycle.cabal +8/−3
• src/RandomCycle/List.hs +14/−8
• src/RandomCycle/Vector.hs +4/−1
• src/RandomCycle/Vector/Cycle.hs +23/−8
• src/RandomCycle/Vector/Partition.hs +3/−1

@@ -1,5 +1,9 @@ # Revision history for random-cycle +## 0.1.0.1 -- 2023-04-18++* Documentation fixes and base package bounds loosened.+ ## 0.1.0.0 -- 2023-04-17  * First version. Released on an unsuspecting world.

@@ -21,11 +21,16 @@ σ -> (i, σ(i))  , for i = 1..|V|  defines a bijective map between the permutations σ  on |V| distinct elements-and the edge sets of C(V).+and the edge sets of C(V). Therefore, sampling a uniform cycle partition+without conditions is as simple as sampling a uniform permutation.  Note self-loops are allowed in the possible configurations. -<!--TODO: sampling with conditions-->+`uniformCyclePartitionThin` samples uniformly from the set of cycle partition+graphs satisfying a predicate, in O(n/p) time on average, where p is the+proportion of cycle partition graphs satisfying the predicate. It works by+rejection sampling, so the user is asked to provide a maximum number of+sampling attempts to guarantee termination.  ## List or vector partitions This package provides functions to draw uniform samples from all 2^(n-1)@@ -37,16 +42,14 @@  Only the partitioning is randomized: Input list order is preserved. -At the moment, the `uniformPartitionThin` is implemented only for lists: It-works by rejection sampling and hence will not terminate if `p` is effectively-zero.- The samplers randomize the placement of each breakpoint in the partition. In other words the sample space is viewed as a perfect binary tree, and random selection is a random walk from root to leaf. The implementation samples a bit array to determine the walk path instead of creating an actual tree structure, for efficiency. +At the moment, the `uniformPartitionThin` is implemented only for lists.+ ### Short-circuiting The predicate provided to `uniformPartitionThin` checks each partition element, a chunk of elements in the original list, in turn. Since partitions are built@@ -54,7 +57,7 @@ the first partition element for which the predicate is `False`. This is just a consequence of the short-circuiting in `base` package function `all`. -In addition, if the predicate itself is short-circuiting, the sampler will+Similarly, if the predicate itself is short-circuiting, the sampler will short-circuit.  ## Contributing

@@ -1,6 +1,6 @@ cabal-version:      2.4 name:               random-cycle-version:            0.1.0.0+version:            0.1.0.1 synopsis: Uniform draws of partitions and cycle-partitions, with thinning.  description: @@ -8,6 +8,11 @@     graphs on sets of vertices, and partitions of lists or vectors. Selection     can be subject to conditions. +-- The ones tested in the CI, on linux x86_64.+-- Base package range indicates other compilers tested locally.+tested-with:+    ghc == 9.2.5+ homepage: https://sr.ht/~brendanrbrown/random-cycle bug-reports: https://todo.sr.ht/~brendanrbrown/random-cycle license: GPL-3.0-or-later@@ -28,7 +33,7 @@       RandomCycle.Vector.Partition       RandomCycle.Vector.Cycle     build-depends:    -      base ^>=4.16.3.0+      base >=4.14.3.0 && <= 4.17.0.0       , primitive       , mwc-random       , random@@ -71,7 +76,7 @@     -- LANGUAGE extensions used by modules in this package.     -- other-extensions:     build-depends:    -      base ^>=4.16.3.0+      base >=4.14.3.0 && <= 4.17.0.0       , random-cycle       , algebraic-graphs       , tasty

@@ -1,10 +1,13 @@ module RandomCycle.List-  ( uniformPartition,+  ( -- * Partitions+    uniformPartition,     uniformPartitionThin,-    uniformCyclePartition,-    uniformCyclePartitionThin,     partitionLengths,     partitionFromBits,++    -- * Cycles+    uniformCyclePartition,+    uniformCyclePartitionThin,   ) where @@ -14,22 +17,25 @@ import qualified RandomCycle.Vector as RV import System.Random.Stateful (StatefulGen) --- | Sample a cycle graph partition of '[0.. n-1]',--- uniformly over the \(n!\) possibilities. The list implementation--- is a convenenience wrapper around 'RandomCycle.Vector.uniformCyclePartition'.+-- | 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 = do   v <- RV.uniformCyclePartition n g   pure $ V.toList v --- | Sample a cycle graph partition of '[0.. n-1]',+-- | Sample a cycle graph partition of @[0.. n-1]@, -- uniformly over the set satisfying the conditions.--- The list implementation is a convenenience wrapper around+-- 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)])

@@ -1,6 +1,9 @@ module RandomCycle.Vector-  ( uniformPartition,+  ( -- * Partitions+    uniformPartition,     partitionFromBits,++    -- * Cycles     uniformCyclePartition,     uniformCyclePartitionThin,   )

@@ -49,15 +49,15 @@ -- TODO: uniform (full) cycle with [Sattolo's algorithm](https://algo.inria.fr/seminars/summary/Wilson2004b.pdf) -- uniformCycle --- | Select a partition of '[0..n-1]' into disjoint+-- | Select a partition of @[0..n-1]@ into disjoint --  [cycle graphs](https://en.wikipedia.org/wiki/Cycle_graph),---  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}\). In other words,+--  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}/. In other words, --  the cycle partition graphs are isomorphic with the rotation matrices. -- --  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'+--  indices. The returned value is a vector of edges. /O(n)/, since 'uniformPermutation' --  implements the [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). -- --  'uniformPermutation' uses in-place mutation, so this function must be run in a 'PrimMonad'@@ -66,7 +66,7 @@ -- ==== __Examples__ -- -- >>> import System.Random.Stateful--- >>> import RandomCycle.Vector+-- >>> 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)]@@ -83,7 +83,7 @@ -- current implementation is the lazy one (as in human-lazy). note that would require -- posting a notice in this module in accordance with the BSD2 license of mwc-random. --- | Uniform selection of a cycle partition graph of '[0..n-1]' elements,+-- | 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. --@@ -96,13 +96,28 @@ -- 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+-- 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) =>+  -- | 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 (V.Vector (Int, Int)))

@@ -28,6 +28,8 @@ -- -- See 'RandomCycle.List.partitionFromBits' for other examples. --+-- ==== __Examples__+-- -- >>> import qualified Data.Vector as V -- >>> partitionFromBits 5 (V.fromList [0..2::Int]) -- [[0],[1],[2]]@@ -47,7 +49,7 @@  {- RANDOM -} --- | Draw a random partition of the input vector 'xs' from the uniform+-- | 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/.