home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2819 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  2.0 KB
  1. Xref: sparky comp.theory:2819 sci.crypt:6490 sci.math:17797 rec.puzzles:8266
  2. Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
  3. Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!batcomputer!cornell!karr
  4. From: karr@cs.cornell.edu (David Karr)
  5. Subject: Re: Looking for random permutation generation algorithms
  6. Message-ID: <1993Jan7.165939.11149@cs.cornell.edu>
  7. Organization: Cornell Univ. CS Dept, Ithaca NY 14853
  8. References: <1993Jan6.014749.15323@ee.ubc.ca>
  9. Date: Thu, 7 Jan 1993 16:59:39 GMT
  10. Lines: 36
  11.  
  12. In article <1993Jan6.014749.15323@ee.ubc.ca> rayw@ee.ubc.ca (raymond w m woo) writes:
  13. >Hi, does anyone know, or can provide any pointer in the literature to, any 
  14. >random permutation generation algorithm that can be easily implemented as a 
  15. >function in a computer program?  
  16. >
  17. >Ideally, this function would be computationally effective, and the input 
  18. >that this function takes would be some kind of index/rank number of the
  19. >permution to be generated.  
  20.  
  21. How about the following (I am trying to generate all permutations of the
  22. integers 1, ..., N):
  23.  
  24. Start with an array v[1..N] with v[i]=i for each i.  The input is an
  25. integer k from 1 to N! (N factorial).  Set t=N (highest entry in v)
  26. and p=0 (first open slot in output array w[1..N]).
  27.  
  28. Now for b = N down to 2, take i = k mod b.  Copy v[i] to w[p],
  29. increment p, copy v[t] to v[i], decrement t.  Essentially this has
  30. just removed the i-th element of v, adding it to the output and
  31. shrinking v accordingly.
  32.  
  33. When this is done there will be only one unused element left in v, at
  34. v[1].  Copy it to w[N].
  35.  
  36. The running time of this algorithm should be approximately
  37. proportional to N.
  38.  
  39. This should produce all N! possible orderings of the integers 1,...,N,
  40. and any input in the legal range produces a unique permutation.  If
  41. you like you can replace the integers 1 to N in array v with some
  42. other data that you wish to permute, but the permutations will be
  43. unique only if your data contains no duplicates.
  44.  
  45. -- David Karr (karr@cs.cornell.edu)
  46.  
  47.  
  48.