Re: [Haskell-cafe] Acquiring a random set of a specific size (w/o dups) from a range of Ints

newer
Dead else branch does influence...

michael rice

13 Jun 2011 13 Jun '11

10:31 p.m.

Thanks, all. It seemed like something like this should exist in a prob/stat package, and if so, didn't want to reinvent the wheel. Shuffle [1..20], then take 5? Yes, so simple, I'm embarrassed I didn't think of it. Michael --- On Mon, 6/13/11, Felipe Almeida Lessa wrote: From: Felipe Almeida Lessa Subject: Re: [Haskell-cafe] Acquiring a random set of a specific size (w/o dups) from a range of Ints To: "michael rice" Cc: haskell-cafe@haskell.org Date: Monday, June 13, 2011, 9:38 PM On Mon, Jun 13, 2011 at 8:56 PM, michael rice wrote:

...

Is there an (existing) way to select 5 Ints randomly (no duplicates) from a population, say 1-20 (inclusive)?

Attachments:

attachment.html (text/html — 3.3 KB)

Show replies by date

michael rice

13 Jun 13 Jun

10:44 p.m.

New subject: Acquiring a random set of a specific size (w/o dups) from a range of Ints

Reason why this doesn't work? Michael ========== [michael@sabal ~]$ cabal install monte-carloResolving dependencies...Downloading primitive-0.3.1...Configuring primitive-0.3.1...Preprocessing library primitive-0.3.1...Building primitive-0.3.1...[1 of 7] Compiling Data.Primitive.MachDeps ( Data/Primitive/MachDeps.hs, dist/build/Data/Primitive/MachDeps.o )[2 of 7] Compiling Control.Monad.Primitive ( Control/Monad/Primitive.hs, dist/build/Control/Monad/Primitive.o ) Control/Monad/Primitive.hs:24:1: Warning: Module `GHC.IOBase' is deprecated: use GHC.IO instead[3 of 7] Compiling Data.Primitive.Types ( Data/Primitive/Types.hs, dist/build/Data/Primitive/Types.o ) Data/Primitive/Types.hs:39:30: Warning: In the use of `mkNorepType' (imported from Data.Data): Deprecated: "Use mkNoRepType instead"[4 of 7] Compiling Data.Primitive.Array ( Data/Primitive/Array.hs, dist/build/Data/Primitive/Array.o ) Data/Primitive/Array.hs:27:30: Warning: In the use of `mkNorepType' (imported from Data.Data): Deprecated: "Use mkNoRepType instead"[5 of 7] Compiling Data.Primitive.ByteArray ( Data/Primitive/ByteArray.hs, dist/build/Data/Primitive/ByteArray.o ) Data/Primitive/ByteArray.hs:36:30: Warning: In the use of `mkNorepType' (imported from Data.Data): Deprecated: "Use mkNoRepType instead"[6 of 7] Compiling Data.Primitive.Addr ( Data/Primitive/Addr.hs, dist/build/Data/Primitive/Addr.o )[7 of 7] Compiling Data.Primitive ( Data/Primitive.hs, dist/build/Data/Primitive.o )Registering primitive-0.3.1...Installing library in /home/michael/.cabal/lib/primitive-0.3.1/ghc-7.0.2Registering primitive-0.3.1...Downloading vector-0.7.0.1...Configuring vector-0.7.0.1...Preprocessing library vector-0.7.0.1...Building vector-0.7.0.1...[ 1 of 19] Compiling Data.Vector.Storable.Internal ( Data/Vector/Storable/Internal.hs, dist/build/Data/Vector/Storable/Internal.o )[ 2 of 19] Compiling Data.Vector.Fusion.Util ( Data/Vector/Fusion/Util.hs, dist/build/Data/Vector/Fusion/Util.o )[ 3 of 19] Compiling Data.Vector.Fusion.Stream.Size ( Data/Vector/Fusion/Stream/Size.hs, dist/build/Data/Vector/Fusion/Stream/Size.o ) Data/Vector/Fusion/Stream/Size.hs:25:10: Warning: No explicit method nor default method for `*' In the instance declaration for `Num Size' Data/Vector/Fusion/Stream/Size.hs:25:10: Warning: No explicit method nor default method for `abs' In the instance declaration for `Num Size' Data/Vector/Fusion/Stream/Size.hs:25:10: Warning: No explicit method nor default method for `signum' In the instance declaration for `Num Size'[ 4 of 19] Compiling Data.Vector.Internal.Check ( Data/Vector/Internal/Check.hs, dist/build/Data/Vector/Internal/Check.o )[ 5 of 19] Compiling Data.Vector.Fusion.Stream.Monadic ( Data/Vector/Fusion/Stream/Monadic.hs, dist/build/Data/Vector/Fusion/Stream/Monadic.o )Loading package ghc-prim ... linking ... done.Loading package integer-gmp ... linking ... done.Loading package base ... linking ... done.Loading package primitive-0.3.1 ... linking ... done.[ 6 of 19] Compiling Data.Vector.Fusion.Stream ( Data/Vector/Fusion/Stream.hs, dist/build/Data/Vector/Fusion/Stream.o )[ 7 of 19] Compiling Data.Vector.Generic.Mutable ( Data/Vector/Generic/Mutable.hs, dist/build/Data/Vector/Generic/Mutable.o )[ 8 of 19] Compiling Data.Vector.Generic.Base ( Data/Vector/Generic/Base.hs, dist/build/Data/Vector/Generic/Base.o )[ 9 of 19] Compiling Data.Vector.Generic.New ( Data/Vector/Generic/New.hs, dist/build/Data/Vector/Generic/New.o )[10 of 19] Compiling Data.Vector.Generic ( Data/Vector/Generic.hs, dist/build/Data/Vector/Generic.o ) Data/Vector/Generic.hs:185:36: Warning: In the use of `mkNorepType' (imported from Data.Data): Deprecated: "Use mkNoRepType instead"[11 of 19] Compiling Data.Vector.Primitive.Mutable ( Data/Vector/Primitive/Mutable.hs, dist/build/Data/Vector/Primitive/Mutable.o )[12 of 19] Compiling Data.Vector.Primitive ( Data/Vector/Primitive.hs, dist/build/Data/Vector/Primitive.o )[13 of 19] Compiling Data.Vector.Storable.Mutable ( Data/Vector/Storable/Mutable.hs, dist/build/Data/Vector/Storable/Mutable.o )[14 of 19] Compiling Data.Vector.Storable ( Data/Vector/Storable.hs, dist/build/Data/Vector/Storable.o )[15 of 19] Compiling Data.Vector.Unboxed.Base ( Data/Vector/Unboxed/Base.hs, dist/build/Data/Vector/Unboxed/Base.o )[16 of 19] Compiling Data.Vector.Unboxed ( Data/Vector/Unboxed.hs, dist/build/Data/Vector/Unboxed.o )[17 of 19] Compiling Data.Vector.Unboxed.Mutable ( Data/Vector/Unboxed/Mutable.hs, dist/build/Data/Vector/Unboxed/Mutable.o )[18 of 19] Compiling Data.Vector.Mutable ( Data/Vector/Mutable.hs, dist/build/Data/Vector/Mutable.o )[19 of 19] Compiling Data.Vector ( Data/Vector.hs, dist/build/Data/Vector.o )Registering vector-0.7.0.1...Installing library in /home/michael/.cabal/lib/vector-0.7.0.1/ghc-7.0.2Registering vector-0.7.0.1...Downloading gsl-random-0.4.3...[1 of 1] Compiling Main ( /tmp/gsl-random-0.4.32479/gsl-random-0.4.3/Setup.lhs, /tmp/gsl-random-0.4.32479/gsl-random-0.4.3/dist/setup/Main.o )Linking /tmp/gsl-random-0.4.32479/gsl-random-0.4.3/dist/setup/setup ...Configuring gsl-random-0.4.3...setup: The program gsl-config is required but it could not be found.cabal: Error: some packages failed to install:gsl-random-0.4.3 failed during the configure step. The exception was:ExitFailure 1monte-carlo-0.4.1 depends on gsl-random-0.4.3 which failed to install.[michael@sabal ~]$ ghciGHCi, version 7.0.2: http://www.haskell.org/ghc/ :? for helpLoading package ghc-prim ... linking ... done.Loading package integer-gmp ... linking ... done.Loading package base ... linking ... done.Prelude> :m + Control.Monad.MC.Class <no location info>: Could not find module `Control.Monad.MC.Class': it is not a module in the current program, or in any known package.Prelude> --- On Mon, 6/13/11, michael rice wrote: From: michael rice Subject: Re: [Haskell-cafe] Acquiring a random set of a specific size (w/o dups) from a range of Ints To: "Felipe Almeida Lessa" Cc: haskell-cafe@haskell.org Date: Monday, June 13, 2011, 10:31 PM Thanks, all. It seemed like something like this should exist in a prob/stat package, and if so, didn't want to reinvent the wheel. Shuffle [1..20], then take 5? Yes, so simple, I'm embarrassed I didn't think of it. Michael --- On Mon, 6/13/11, Felipe Almeida Lessa wrote: From: Felipe Almeida Lessa Subject: Re: [Haskell-cafe] Acquiring a random set of a specific size (w/o dups) from a range of Ints To: "michael rice" Cc: haskell-cafe@haskell.org Date: Monday, June 13, 2011, 9:38 PM On Mon, Jun 13, 2011 at 8:56 PM, michael rice wrote:

...

Is there an (existing) way to select 5 Ints randomly (no duplicates) from a population, say 1-20 (inclusive)?

Yes, already implemented in the monte-carlo package as sampleSubset [1], sampleSubset :: MonadMC m => [a] -> Int -> m [a] Complete example code for your example: evalMC (sampleSubset [1..20] 5) (mt19937 0) Cheers! [1] http://hackage.haskell.org/packages/archive/monte-carlo/0.4.1/doc/html/Contr... -- Felipe. -----Inline Attachment Follows----- _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Felipe Almeida Lessa

10:45 p.m.

New subject: Acquiring a random set of a specific size (w/o dups) from a range of Ints

On Mon, Jun 13, 2011 at 11:44 PM, michael rice wrote:

...

Downloading gsl-random-0.4.3... [1 of 1] Compiling Main ( /tmp/gsl-random-0.4.32479/gsl-random-0.4.3/Setup.lhs, /tmp/gsl-random-0.4.32479/gsl-random-0.4.3/dist/setup/Main.o ) Linking /tmp/gsl-random-0.4.32479/gsl-random-0.4.3/dist/setup/setup ... Configuring gsl-random-0.4.3... setup: The program gsl-config is required but it could not be found. cabal: Error: some packages failed to install: gsl-random-0.4.3 failed during the configure step. The exception was: ExitFailure 1

You have to install GSL development packages on your system. Cheers, -- Felipe.

michael rice

11:52 p.m.

New subject: Acquiring a random set of a specific size (w/o dups) from a range of Ints

And then reinstall the monte-carlo? Michael --- On Mon, 6/13/11, Felipe Almeida Lessa wrote: From: Felipe Almeida Lessa Subject: Re: [Haskell-cafe] Acquiring a random set of a specific size (w/o dups) from a range of Ints To: "michael rice" Cc: haskell-cafe@haskell.org Date: Monday, June 13, 2011, 10:45 PM On Mon, Jun 13, 2011 at 11:44 PM, michael rice wrote:

...

Downloading gsl-random-0.4.3... [1 of 1] Compiling Main ( /tmp/gsl-random-0.4.32479/gsl-random-0.4.3/Setup.lhs, /tmp/gsl-random-0.4.32479/gsl-random-0.4.3/dist/setup/Main.o ) Linking /tmp/gsl-random-0.4.32479/gsl-random-0.4.3/dist/setup/setup ... Configuring gsl-random-0.4.3... setup: The program gsl-config is required but it could not be found. cabal: Error: some packages failed to install: gsl-random-0.4.3 failed during the configure step. The exception was: ExitFailure 1

You have to install GSL development packages on your system. Cheers, -- Felipe.

Jonas Almström Duregård

14 Jun 14 Jun

5:17 a.m.

New subject: Acquiring a random set of a specific size (w/o dups) from a range of Ints

...

Shuffle [1..20], then take 5? Yes, so simple, I'm embarrassed I didn't think of it.

...

Thanks, all.

It seemed like something like this should exist in a prob/stat package, and if so, didn't want to reinvent the wheel.

Shuffle [1..20], then take 5?

Yes, so simple, I'm embarrassed I didn't think of it.

Michael

--- On *Mon, 6/13/11, Felipe Almeida Lessa *wrote:

From: Felipe Almeida Lessa Subject: Re: [Haskell-cafe] Acquiring a random set of a specific size (w/o dups) from a range of Ints To: "michael rice" Cc: haskell-cafe@haskell.org Date: Monday, June 13, 2011, 9:38 PM

On Mon, Jun 13, 2011 at 8:56 PM, michael rice wrote:

...
Is there an (existing) way to select 5 Ints randomly (no duplicates) from a population, say 1-20 (inclusive)?

Yes, already implemented in the monte-carlo package as sampleSubset [1],

sampleSubset :: MonadMC m => [a] -> Int -> m [a]

Complete example code for your example:

evalMC (sampleSubset [1..20] 5) (mt19937 0)

Cheers!

[1] http://hackage.haskell.org/packages/archive/monte-carlo/0.4.1/doc/html/Contr...

-- Felipe.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

michael rice

7:35 a.m.

New subject: Acquiring a random set of a specific size (w/o dups) from a range of Ints

I had the same thought, since my interval [1..10000] is rather large. Thanks, MIchael --- On Tue, 6/14/11, Jonas Almström Duregård wrote: From: Jonas Almström Duregård Subject: Re: [Haskell-cafe] Acquiring a random set of a specific size (w/o dups) from a range of Ints To: "michael rice" Cc: "Felipe Almeida Lessa" , haskell-cafe@haskell.org Date: Tuesday, June 14, 2011, 5:17 AM

...

Shuffle [1..20], then take 5? Yes, so simple, I'm embarrassed I didn't think of it.

That works well for small numbers, but I'm guessing it will evaluate the entire list so it should not be used for large inputs. If you have a large interval and use a relatively small part of it, the following function should be significantly faster (it builds a random permutation lazily): import System.Random randomOrder :: (Ord a, Num a, Random a, RandomGen g) => (a,a) -> g -> [a]randomOrder (low,high) g | low > high = [] | otherwise = let (a,g') = randomR (low,high) g (gl,gr) = split g' in a : mergeRandom (a-1-low,randomOrder (low,a-1) gl) (high-a-1, randomOrder (a+1,high) gr) g' where mergeRandom (_,[]) (_,xs) _ = xs mergeRandom (_,xs) (_,[]) _ = xs mergeRandom (lx,x:xs) (ly,y:ys) g = let (pick,g') = randomR (1,lx + ly) g in if pick <= lx then x : mergeRandom (lx-1,xs) (ly,y:ys) g' else y : mergeRandom (lx,x:xs) (ly-1,ys) g' On 14 June 2011 04:31, michael rice wrote: Thanks, all. It seemed like something like this should exist in a prob/stat package, and if so, didn't want to reinvent the wheel. Shuffle [1..20], then take 5? Yes, so simple, I'm embarrassed I didn't think of it. Michael --- On Mon, 6/13/11, Felipe Almeida Lessa wrote: From: Felipe Almeida Lessa Subject: Re: [Haskell-cafe] Acquiring a random set of a specific size (w/o dups) from a range of Ints To: "michael rice" Cc: haskell-cafe@haskell.org Date: Monday, June 13, 2011, 9:38 PM On Mon, Jun 13, 2011 at 8:56 PM, michael rice wrote:

...

Is there an (existing) way to select 5 Ints randomly (no duplicates) from a population, say 1-20 (inclusive)?

Yes, already implemented in the monte-carlo package as sampleSubset [1], sampleSubset :: MonadMC m => [a] -> Int -> m [a] Complete example code for your example: evalMC (sampleSubset [1..20] 5) (mt19937 0) Cheers! [1] http://hackage.haskell.org/packages/archive/monte-carlo/0.4.1/doc/html/Contr... -- Felipe. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

5094

Age (days ago)

5094

Last active (days ago)

List overview

Download

5 comments

3 participants

participants (3)

Felipe Almeida Lessa
Jonas Almström Duregård
michael rice