home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2828 < prev    next >
Encoding:
Internet Message Format  |  1993-01-08  |  1.1 KB
  1. Xref: sparky comp.theory:2828 sci.crypt:6534 sci.math:17832 rec.puzzles:8283
  2. Path: sparky!uunet!usna!math3!mdm
  3. From: mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>)
  4. Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
  5. Subject: Re: Looking for random permutation generation algorithms
  6. Message-ID: <2607@usna.NAVY.MIL>
  7. Date: 8 Jan 93 14:47:30 GMT
  8. References: <1993Jan6.014749.15323@ee.ubc.ca> <1993Jan7.165939.11149@cs.cornell.edu>
  9. Sender: news@usna.NAVY.MIL
  10. Reply-To: mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>)
  11. Followup-To: comp.theory
  12. Lines: 11
  13.  
  14. This method fails.  There is a minor error in that letting
  15. p=0 and using modular arithmetic gives zero values outside
  16. of the subscript range of the arrays.  This is easily 
  17. patched.  But a major error is that  k mod b  won't 
  18. distinguish between different k.  The first example of this
  19. failure is for N=4 and k=4 or 16 (N!=24 so both k values occur.)
  20. Then   k mod b  is the same for either  k  and for any
  21. b  from  1  to  N .  Thus when  N=4  this algorithm repeats
  22. certain permutations  (arrays  w ) and so misses some
  23. permutations.
  24.  
  25.