Article View: comp.lang.functional
Article #1070Re: Random permutations, linear time, fully functional?
From: Doug Quale
Date: Sun, 10 Jan 1993 08:09
Date: Sun, 10 Jan 1993 08:09
30 lines
1333 bytes
1333 bytes
In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:
>/*
> * source and result are arrays of integers of length n.
> * For random permutations, source should be made up of a lot of
> * random numbers each between 0 and n-1.
> */
>
>void randpermute(source, result, n)
>int *source, *result, n;
>{
> int i, tmp;
>
> for(i = 0; i < n; i++)
> result[i] = i;
> for(i = 0; i < n; i++) {
> tmp = result[i];
> result[i] = result[source[i]];
> result[source[i]] = tmp;
> }
>}
>
This C code does not solve the problem correctly. The procedure
does not produce a random distribution because the number of possible
shuffles, n**n, is not divisible by the number of permutations, n!.
For instance, the output is skewed for n = 3 (try it!).
--
Doug Quale
quale@saavik.cs.wisc.edu
Technical Details
Message-ID:
<1993Jan10.080957.10407@daffy.cs.wisc.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!daffy!spock.cs.wisc.edu!qualeReferences:
<C0KG2y.HvE@dcs.ed.ac.uk>Show Full Headers
Complete Article Headers
Newsgroups: comp.lang.functional Path: arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!daffy!spock.cs.wisc.edu!quale From: quale@spock.cs.wisc.edu (Doug Quale) Subject: Re: Random permutations, linear time, fully functional? Message-ID: <1993Jan10.080957.10407@daffy.cs.wisc.edu> Sender: news@daffy.cs.wisc.edu (The News) Reply-To: quale@saavik.cs.wisc.edu Organization: University of Wisconsin -- Madison References: <C0KG2y.HvE@dcs.ed.ac.uk> Date: Sun, 10 Jan 1993 08:09:57 GMT Lines: 30