[m-dev.] diff: random permutations

[Ralph Becket]

> From: Fergus Henderson [mailto:fjh at cs.mu.OZ.AU]
> Sent: 09 February 2000 04:54
> 
> On 04-Jan-2000, Ralph Becket <rbeck at microsoft.com> wrote:
> >
> > I agree, although there may well be a place for predicates computing
> > 	(3) random samples of integers in a range and
> > 	(4) random permutations of the above.
> 
> I presume by (4) you mean
> 
>  	(4) random permutations of integers in a range
> 
> not
> 
> 	(4') random permutations of random samples of integers 
> in a range
> 
> since (4') would be equivalent to (3).

I wasn't being very clear.  By (3) I meant an (ordered) random 
sample without replacement from a range, such as any ordered
subset of 5 numbers from [3..14], say.  This can be done in 
O(nlogn) time.

By (4) I meant (3) in some random permutation, which can also
be constructed in O(nlogn) time.

Since these algorithms are relatively easy to implement and the
sort of thing one could imagine using with fair frequency when
dealing with random numbers, I thought it might be sensible to
include them in the library.

Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------