home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2849 < prev    next >
Encoding:
Internet Message Format  |  1993-01-10  |  2.0 KB
  1. Xref: sparky comp.theory:2849 sci.crypt:6603 sci.math:17912 rec.puzzles:8312
  2. Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!think.com!linus!philabs!acheron!scifi!watson!yktnews!admin!wo0z!lwloen
  4. From: lwloen@rchland.vnet.ibm.com (Larry Loen)
  5. Subject: Re: Looking for random permutation generation algorithms
  6. Sender: news@rchland.ibm.com
  7. Message-ID: <1993Jan09.220921.19430@rchland.ibm.com>
  8. Date: Sat, 09 Jan 1993 22:09:21 GMT
  9. Reply-To: lwloen@rchland.vnet.ibm.com
  10. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  11. References: <1993Jan6.014749.15323@ee.ubc.ca> <1993Jan6.224804.6116@dsuvax.dsu.edu>
  12. Nntp-Posting-Host: wo0z.rchland.ibm.com
  13. Organization: IBM Rochester
  14. Lines: 29
  15.  
  16.  
  17. If I understand the request correctly, the original poster is looking
  18. for a way of generating a pseudo random string of digits including all
  19. number 0, 1. . . n-1 for n numbers, without repeating any.
  20.  
  21. The simplest way to do this comes from APL.  What you do is generate
  22. a string of n numbers using any suitable random number generator.
  23.  
  24. Then, you do a "sort" of the numbers using the "index array" method.
  25.  
  26. That is, you leave the original numbers in place, and sort an array
  27. of "indexes" to the original data.
  28.  
  29. As it happens, that sorted array will, itself, provide the array
  30. required.  In other words, the original random numbers (that may have
  31. had repeats) is discarded after the sort, because they were merely means
  32. to an end.
  33.  
  34. Now, if that doesn't quite "cut" what is looked for, here, such an array
  35. can probably be used to manipulate some sort of starting permutation
  36. in a pseudo-random way with only a little more thought.  However, since
  37. the numbers don't repeat, it would seem to form a permutation-substitution
  38. by simply having index i replaced by index i+1 and so forth.
  39.  
  40. If one has a built-in sort handy, it is very easy to do.
  41.  
  42. -- 
  43.    Larry W. Loen        |  My Opinions are decidedly my own, so please
  44.                         |  do not attribute them to my employer
  45.