home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2830 < prev    next >
Encoding:
Internet Message Format  |  1993-01-08  |  2.1 KB
  1. Xref: sparky comp.theory:2830 sci.crypt:6539 sci.math:17847 rec.puzzles:8284
  2. Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
  3. Path: sparky!uunet!gatech!rpi!batcomputer!cornell!karr
  4. From: karr@cs.cornell.edu (David Karr)
  5. Subject: Re: Looking for random permutation generation algorithms
  6. Message-ID: <1993Jan8.163909.20820@cs.cornell.edu>
  7. Organization: Cornell Univ. CS Dept, Ithaca NY 14853
  8. References: <1993Jan6.014749.15323@ee.ubc.ca> <1993Jan7.165939.11149@cs.cornell.edu> <2607@usna.NAVY.MIL>
  9. Date: Fri, 8 Jan 1993 16:39:09 GMT
  10. Lines: 37
  11.  
  12. Aaargh.  Somehow, in my effort to get the permutation algorithm
  13. from my head to a clear written explanation, I managed to flub 
  14. at least two key points.  Prof. Meyerson points out both of them:
  15.  
  16. In article <2607@usna.NAVY.MIL> mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>) writes:
  17. >This method fails.  There is a minor error in that letting
  18. >p=0 and using modular arithmetic gives zero values outside
  19. >of the subscript range of the arrays.  This is easily 
  20. >patched.
  21.  
  22. True.  I should have indexed both arrays v and w from 0 to N-1 in the
  23. first place, and initialized t to N-1 as well.  I hope this fixes this
  24. error.
  25.  
  26. >  But a major error is that  k mod b  won't 
  27. >distinguish between different k.  The first example of this
  28. >failure is for N=4 and k=4 or 16 (N!=24 so both k values occur.)
  29.  
  30. This is really the major omission from the algorithm.  I had meant
  31. to compute both k mod b *and* k div b.  k mod b is used to index the
  32. array for the current selection; k div b is then copied to k for the
  33. next round.
  34.  
  35. With the division step properly included in the algorithm, the
  36. resulting permutations for k=4 and k=16 are 1,4,3,2 and 1,2,4,3
  37. respectively.  If you get different results then most likely I have
  38. made some other error in the description of the algorithm.
  39.  
  40. Actually I suspect my algorithm may be fundamentally the same as
  41. another one that was posted that was supposedly based on FORTRAN
  42. multidimensional array indexing, but I came down with a bad case of
  43. MEGO when I looked at the FORTRAN code so I can't say for sure.
  44.  
  45. -- David Karr (karr@cs.cornell.edu)
  46.  
  47.  
  48.  
  49.