Re: Looking for random permutation generation algorithms

Article View: comp.theory

Article #1913

#1913

From: Mark D. Meyerson -- math FACULTY...
Date: Fri, 08 Jan 1993 14:47

10 lines
1112 bytes

This method fails.  There is a minor error in that letting
p=0 and using modular arithmetic gives zero values outside
of the subscript range of the arrays.  This is easily 
patched.  But a major error is that  k mod b  won't 
distinguish between different k.  The first example of this
failure is for N=4 and k=4 or 16 (N!=24 so both k values occur.)
Then   k mod b  is the same for either  k  and for any
b  from  1  to  N .  Thus when  N=4  this algorithm repeats
certain permutations  (arrays  w ) and so misses some
permutations.

Technical Details

Message-ID: <2607@usna.NAVY.MIL>

Path: arc1-ca.pugleaf.net!sparky!uunet!usna!math3!mdm

References: <1993Jan6.014749.15323@ee.ubc.ca> <1993Jan7.165939.11149@cs.cornell.edu>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!sparky!uunet!usna!math3!mdm
From: mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>)
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
Subject: Re: Looking for random permutation generation algorithms
Message-ID: <2607@usna.NAVY.MIL>
Date: 8 Jan 93 14:47:30 GMT
References: <1993Jan6.014749.15323@ee.ubc.ca> <1993Jan7.165939.11149@cs.cornell.edu>
Sender: news@usna.NAVY.MIL
Reply-To: mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>)
Followup-To: comp.theory
Lines: 11

Reply to Parent Message