Article View: comp.lang.functional
Article #1069Re: Random permutations, linear time, fully functional?
From: Doug Quale
Date: Sun, 10 Jan 1993 08:01
Date: Sun, 10 Jan 1993 08:01
30 lines
1243 bytes
1243 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. It gives n**n
possible outcomes, and in general the number of permutations of n
objects, n!, does not divide n**n. For example, it doesn't work
for n = 3 (try it!).
--
Doug Quale
quale@saavik.cs.wisc.edu
Technical Details
Message-ID:
<1993Jan10.080153.10321@daffy.cs.wisc.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!spool.mu.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!spool.mu.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.080153.10321@daffy.cs.wisc.edu> Sender: news@daffy.cs.wisc.edu (The News) Organization: University of Wisconsin -- Madison References: <C0KG2y.HvE@dcs.ed.ac.uk> Date: Sun, 10 Jan 1993 08:01:53 GMT Lines: 30