RE: Random Permutations

2003-03-07 Thread Jacques Carette
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

Re: Random Permutations

2003-03-06 Thread Jerzy Karczmarczuk
[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

Re: Random Permutations

2003-03-06 Thread oleg
> 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

Re: random permutations

2003-03-06 Thread Dimitre Novatchev
--- 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

Re: random permutations

2003-03-06 Thread George Russell
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 $ \_ _

Re: Random Permutations

2003-03-06 Thread Matthew Donadio
[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

Re: Random Permutations

2003-03-06 Thread Janis Voigtlaender
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

Re: Random Permutations

2003-03-06 Thread Andreas Abel
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

Re: Random Permutations

2003-03-06 Thread Ralf Hinze
> 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

Re: Random Permutations

2003-03-06 Thread Jerzy Karczmarczuk
[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

Random Permutations

2003-03-06 Thread Markus . Schnell
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