Pertinent to this thread (though perhaps overkill) is the work of Flajolet
et al on (fast) random generation of combinatorial structures for any
structure given as a context-free grammar, including Permutation.
In particular see
http://citeseer.nj.nec.com/flajolet93calculus.html
http://citeseer.nj
[EMAIL PROTECTED] comments my suggestion:
1. Generate N random numbers r_k, say, uniform between 0 and 1.
2. Form N pairs (1,r_1), (2,r_2), (3, r_3) ... (N,r_n).
3. Sort this list/vector wrt the *second* (random) number.
4. In the sorted list the first values (indices) give you the result.
I'm so
> 1. Generate N random numbers r_k, say, uniform between 0 and 1.
> 2. Form N pairs (1,r_1), (2,r_2), (3, r_3) ... (N,r_n).
> 3. Sort this list/vector wrt the *secon* (random) number.
> 4. In the sorted list the firs values (indices) give you the result.
> This is of course quite general, not res
--- George Russell <[EMAIL PROTECTED]> wrote:
> I think Ralf Hinze's method is the best presented so far. I would
> write
> it slightly differently though. In pseudo-code I would proceed as
> follows:
> (1) write the values to an array a[1]..a[n]
> (2) for i from n to 2
> do
>j <- ra
Andreas wrote
Well, sorting is a special case of permuting, so my idea was to use the library
routine
List.sortBy :: (a -> a -> Ordering) -> [a] -> [a]
passing it a comparison function which ignores its arguments and simply returns
a random bit when invoked, e.g.
permute = sortBy $ \_ _
[EMAIL PROTECTED] wrote:
> Is there a library routine for random permutations?
Check out this link:
http://www.nist.gov/dads/HTML/perfectShuffle.html
--
Matthew Donadio ([EMAIL PROTECTED])
___
Haskell mailing list
[EMAIL PROTECTED]
h
Andreas Abel wrote:
> Well, sorting is a special case of permuting, so my idea was to use the library
> routine
>
>List.sortBy :: (a -> a -> Ordering) -> [a] -> [a]
>
> passing it a comparison function which ignores its arguments and simply returns
> a random bit when invoked, e.g.
>
>pe
Is there a library routine for random permutations?
I didn't find any and did a quick hack, which works fine for my
application (length of list < 100), but what would be a more
elegant way?
Well, sorting is a special case of permuting, so my idea was to use the library
routine
Lis
> Is there a library routine for random permutations?
>
> I didn't find any and did a quick hack, which works fine for my
> application (length of list < 100), but what would be a more
> elegant way?
>
> > permute :: StdGen -> [a] -> [a]
> > permute
[EMAIL PROTECTED] wrote:
Is there a library routine for random permutations?
I didn't find any and did a quick hack...
There are many algorithms.
One, quite natural and quite fast
(n log n; slower than linear, though...)
consists in:
1. Generate N random numbers r_k, say, uniform between 0
Is there a library routine for random permutations?
I didn't find any and did a quick hack, which works fine for my
application (length of list < 100), but what would be a more
elegant way?
> permute :: StdGen -> [a] -> [a]
> permute gen [] = []
> permute gen xs = (head
11 matches
Mail list logo