home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / function / 1502 < prev    next >
Encoding:
Text File  |  1993-01-10  |  1.3 KB  |  43 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!daffy!spock.cs.wisc.edu!quale
  3. From: quale@spock.cs.wisc.edu (Doug Quale)
  4. Subject: Re: Random permutations, linear time, fully functional?
  5. Message-ID: <1993Jan10.080957.10407@daffy.cs.wisc.edu>
  6. Sender: news@daffy.cs.wisc.edu (The News)
  7. Reply-To: quale@saavik.cs.wisc.edu
  8. Organization: University of Wisconsin -- Madison
  9. References: <C0KG2y.HvE@dcs.ed.ac.uk>
  10. Date: Sun, 10 Jan 1993 08:09:57 GMT
  11. Lines: 30
  12.  
  13. In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:
  14. >/* 
  15. > * source and result are arrays of integers of length n.
  16. > * For random permutations, source should be made up of a lot of
  17. > * random numbers each between 0 and n-1.
  18. > */
  19. >
  20. >void randpermute(source, result, n)
  21. >int *source, *result, n;
  22. >{
  23. >    int i, tmp;
  24. >    
  25. >    for(i = 0; i < n; i++)
  26. >        result[i] = i;
  27. >    for(i = 0; i < n; i++) {
  28. >        tmp = result[i];
  29. >        result[i] = result[source[i]];
  30. >        result[source[i]] = tmp;
  31. >    }
  32. >}
  33. >
  34.  
  35. This C code does not solve the problem correctly.  The procedure
  36. does not produce a random distribution because the number of possible
  37. shuffles, n**n, is not divisible by the number of permutations, n!.
  38.  
  39. For instance, the output is skewed for n = 3 (try it!).
  40. -- 
  41. Doug Quale
  42. quale@saavik.cs.wisc.edu
  43.