home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / function / 1501 < prev    next >
Encoding:
Text File  |  1993-01-10  |  1.2 KB  |  42 lines
  1. Newsgroups: comp.lang.functional
  2. Path: sparky!uunet!spool.mu.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.080153.10321@daffy.cs.wisc.edu>
  6. Sender: news@daffy.cs.wisc.edu (The News)
  7. Organization: University of Wisconsin -- Madison
  8. References: <C0KG2y.HvE@dcs.ed.ac.uk>
  9. Date: Sun, 10 Jan 1993 08:01:53 GMT
  10. Lines: 30
  11.  
  12. In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:
  13. >
  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.  It gives n**n
  36. possible outcomes, and in general the number of permutations of n
  37. objects, n!, does not divide n**n.  For example, it doesn't work
  38. for n = 3 (try it!).
  39. -- 
  40. Doug Quale
  41. quale@saavik.cs.wisc.edu
  42.