home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2813 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  1.5 KB
  1. Xref: sparky comp.theory:2813 sci.crypt:6474 sci.math:17778 rec.puzzles:8254
  2. Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
  3. Path: sparky!uunet!haven.umd.edu!decuac!pa.dec.com!engage.pko.dec.com!nntpd.lkg.dec.com!ryn.mro4.dec.com!3d.enet.dec.com!roth
  4. From: roth@3d.enet.dec.com (Jim Roth)
  5. Subject: Re: Looking for random permutation generation algorithms
  6. Message-ID: <1993Jan7.002653.21016@ryn.mro4.dec.com>
  7. Sender: news@ryn.mro4.dec.com (USENET News System)
  8. Organization: Digital Equipment Corporation
  9. Date:  6 JAN 93 19:24:11    
  10. Lines: 27
  11.  
  12.  
  13. In article <1993Jan6.014749.15323@ee.ubc.ca>, rayw@ee.ubc.ca (raymond w m woo) writes...
  14. >Hi, does anyone know, or can provide any pointer in the literature to, any 
  15. >random permutation generation algorithm that can be easily implemented as a 
  16. >function in a computer program?  
  17. > 
  18. >Ideally, this function would be computationally effective, and the input 
  19. >that this function takes would be some kind of index/rank number of the
  20. >permution to be generated.  
  21.  
  22. A coset algorithm works very well for uniformly choosing an element
  23. of a group (in this case the symmetric group.)
  24.  
  25.    initialize n element array a(i) = i
  26.  
  27.    for i = 1 to n-1
  28.        j = random integer from i to n inclusive
  29.        exchange a(i) and a(j)
  30.        (it is possible that i = j and no exchange takes place above)
  31.    end
  32.  
  33.    now a contains a random permutation of n elements
  34.  
  35. This is far nicer than approaches I've seen (such as generating a random
  36. list of numbers, sorting them, and returning the resulting permutation!)
  37.  
  38. - Jim
  39.