home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2809 < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  3.0 KB
  1. Xref: sparky comp.theory:2809 sci.crypt:6458 sci.math:17767 rec.puzzles:8247
  2. Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
  3. Path: sparky!uunet!wupost!dsuvax.dsu.edu!rolfe
  4. From: rolfe@dsuvax.dsu.edu (Tim Rolfe)
  5. Subject: Re: Looking for random permutation generation algorithms
  6. Message-ID: <1993Jan6.224804.6116@dsuvax.dsu.edu>
  7. Organization: Dakota State University
  8. References: <1993Jan6.014749.15323@ee.ubc.ca>
  9. Date: Wed, 6 Jan 1993 22:48:04 GMT
  10. Lines: 86
  11.  
  12. In <1993Jan6.014749.15323@ee.ubc.ca> rayw@ee.ubc.ca (raymond w m woo) writes:
  13.  
  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.  
  23. One approach is to consider the offset calculation for an N-dimensional
  24. array with dimensions (N, N-1, ... , 2, 1).  Language purists:  forgive
  25. the language in what follows --- I mis-remembered the question as from
  26. comp.lang.fortran when I worked up the answering code.  I'm assuming
  27. enough Fortran knowledge to do the translation into <current hot lang.>.
  28.  
  29.       subroutine GenPrm (IdxVal, N, Set)
  30. *
  31. * Permutations of N items can be indexed uniquely after the fashion of
  32. * the array off-set calculation for a multidimensional array of dimension
  33. * (N,N-1,N-2,...,2,1)
  34. *
  35. * E.g., if N = 4, offset (column major) is I1*3! + I2*2! + I3*1! + I4
  36. *
  37.       integer IdxVal, N
  38.       integer Set(*)
  39.       integer Idx, Jdx, Work, Temp
  40.       integer OldN, OverFl
  41.       data OldN/-1/
  42.       save OldN, OverFl
  43. *
  44.       if (N .ne. OldN) then
  45.          OldN = N
  46.          OverFl = 1
  47.          do 10 Idx = 2, N
  48.             OverFl = OverFl * Idx
  49.    10    continue
  50.       end if
  51. *
  52. * (1) Initialize the "Set" array with values to be permuted
  53. *
  54.       do 20 Idx = 1, N
  55.          Set(Idx) = Idx
  56.    20 continue
  57. *
  58. * (2) Set up to strip out the "Indices" in the multidimensional reference
  59. *
  60.       Work = mod (IdxVal, OverFl)
  61.       Ndx  = OverFl/N
  62. *
  63. * (3) Isolate those Indexes
  64. *
  65.       do 30 Idx = 1, N-1
  66.          Jdx = Idx + Work / Ndx
  67.          Work = mod (Work, Ndx)
  68.          Ndx = Ndx / (N-Idx)
  69.          Temp = Set(Idx)
  70.          Set(Idx) = Set(Jdx)
  71.          Set(Jdx) = Temp
  72.    30 continue
  73.       end
  74. *
  75.       program TestBed
  76.       parameter (N = 4)
  77.       integer   Set(N)
  78.       integer   Idx, Lim, Tst
  79.       character OutFmt*20
  80. *
  81.       OutFmt = '('//char(N+ichar('0'))//'i5, ''  <--'', i5)'
  82.       Lim = 1
  83.       do 10 Idx = 2, N
  84.          Lim = Lim * Idx
  85.    10 continue
  86.       print *, Lim, ' lines in all:'
  87.       do 20 Idx = 0, Lim-1
  88.          call GenPrm (Idx, N, Set)
  89.          Tst = mod(Idx, 20)
  90.      print OutFmt, Set, Idx
  91.          if (Tst .eq. 19) read '(a1)', TsT
  92.    20 continue
  93.       end
  94. -- 
  95.                                               --- Tim Rolfe
  96.                                            rolfe@dsuvax.dsu.edu
  97.                                             ROLFE@SDNET.BITNET
  98.