home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / function / 1504 < prev    next >
Encoding:
Internet Message Format  |  1993-01-10  |  3.4 KB
  1. Path: sparky!uunet!pipex!doc.ic.ac.uk!uknet!edcastle!dcs.ed.ac.uk!pdc
  2. From: pdc@dcs.ed.ac.uk (Paul Crowley)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Random permutations, linear time, fully functional?
  5. Message-ID: <C0o6HH.2L2@dcs.ed.ac.uk>
  6. Date: 11 Jan 93 03:17:40 GMT
  7. References: <C0KG2y.HvE@dcs.ed.ac.uk> <1993Jan10.080153.10321@daffy.cs.wisc.edu>
  8. Sender: cnews@dcs.ed.ac.uk (UseNet News Admin)
  9. Reply-To: pdc@dcs.ed.ac.uk (Paul Crowley)
  10. Organization: Edinburgh University
  11. Lines: 71
  12.  
  13. Quoting quale@spock.cs.wisc.edu (Doug Quale) in article <1993Jan10.080153.10321@daffy.cs.wisc.edu>:
  14. >In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:
  15. >This C code does not solve the problem correctly.  It gives n**n
  16. >possible outcomes, and in general the number of permutations of n
  17. >objects, n!, does not divide n**n.  For example, it doesn't work
  18. >for n = 3 (try it!).
  19.  
  20. Damn, you're right.  This is more than a little embarassing since I've
  21. been standing by that code all last term.  However six does not divide
  22. nine, so I guess I've got to modify it.  I think it'll work if I make a
  23. slight change to the source array.  This time I'll prove it correct.
  24.  
  25. /* 
  26.  * source and result are arrays of integers of length n.
  27.  * For random permutations, source should be made up of a lot of
  28.  * random numbers such that 0 <= source[i] <= i.
  29.  */
  30.  
  31. void randpermute(source, result, n)
  32. int *source, *result, n;
  33. {
  34.     int i;
  35.     
  36.     for(i = 0; i < n; i++) {
  37. /*
  38.  * Loop invariant: just before the test against n,
  39.  * result[k] for 0 <= k < i is a permutation of the nat. numbers less than i
  40.  * and the permutation is random if source is random as specified.
  41.  * Proof below.
  42.  */
  43.         result[i] = result[source[i]];
  44.         result[source[i]] = i;
  45.     }
  46. }
  47.  
  48. A permutation of length k is random if the probability of it being equal
  49. to a given permutation gperm is 1/(k!).  Base case of the invariant: the
  50. null permutation arises with probability 1 = 1/(0!).
  51.  
  52. Inductive step: supposing the invariant holds for i = k where k < n. 
  53. After the execution of the next two source lines, is the subarray size
  54. k+1 a permutation at all?  This divides into two subcases:
  55.  
  56. * source[k] = k
  57.  
  58. In this case, result[k] ends up being equal to k and the rest of the
  59. array is unchanged; since the rest of the array is a permutation, this
  60. is a permutation.
  61.  
  62. * source[k] < i
  63.  
  64. In this case, result[k] takes some value between 0 and k-1, and the
  65. entry that used to hold that value now holds k.  Since the rest of the
  66. array was a permutation, all the values between 0 and k are still
  67. present and the new subarray is also a permutation.
  68.  
  69. Now, consider the element h in gperm such that gperm[h] = k.  In order
  70. for the resulting subarray to equal gperm, two conditions must hold:
  71. result[k] must equal h, and the old subarray before the loop stepped
  72. around must be equal to gperm except that result[h] must equal gperm[k].
  73. The probability of these two is 1/(k+1) and 1/(k!) respectively, so the
  74. probability that the new subarray is gperm is 1/((k+1)!) as required.
  75.  
  76. Sorry if this isn't very clear but it's 3am where I am.  For people who
  77. want to know what all this C is doing in comp.lang.functional, I asked
  78. if the thing that this C function does in linear time can be done in a
  79. pure functional style in linear time.  Except that I got the C wrong. 
  80. Apologies, and thanks to Doug Quale for pointing it out.
  81.   __                                   _____
  82. \/ o\ Paul Crowley   pdc@dcs.ed.ac.uk  \\ //
  83. /\__/ Trust me. I know what I'm doing.  \X/ 
  84.