home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2839 < prev    next >
Encoding:
Text File  |  1993-01-08  |  3.9 KB  |  128 lines
  1. Xref: sparky comp.theory:2839 sci.crypt:6564 sci.math:17871 rec.puzzles:8297
  2. Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
  3. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!wupost!cs.utexas.edu!asuvax!elam.mdl.sandia.gov!cs.sandia.gov!samitch
  4. From: samitch@cs.sandia.gov (Scott A. Mitchell)
  5. Subject: Re: Looking for random permutation generation algorithms
  6. Message-ID: <1993Jan8.192007.17273@cs.sandia.gov>
  7. Sender: usenet@cs.sandia.gov (Another name for news)
  8. Organization: Sandia National Laboratories, Albuquerque, NM
  9. References: <2607@usna.NAVY.MIL> <1993Jan8.163909.20820@cs.cornell.edu> <1993Jan8.172824.22910@cs.cornell.edu>
  10. Date: Fri, 8 Jan 93 19:20:07 GMT
  11. Lines: 115
  12.  
  13.  
  14. I had the wrong subject heading last time I posted this and the principle
  15. players seemed to have missed it, so here it is again.
  16.  
  17. In article <1993Jan6.014749.15323@ee.ubc.ca> rayw@ee.ubc.ca (raymond w m woo) writes:
  18. >Hi, does anyone know, or can provide any pointer in the literature to, any 
  19. >random permutation generation algorithm that can be easily implemented as a 
  20. >function in a computer program?  
  21. >
  22. >Ideally, this function would be computationally effective, and the input 
  23. >that this function takes would be some kind of index/rank number of the
  24. >permution to be generated.  
  25.  
  26. then karr@cs.cornell.edu (David Karr) describes an alg
  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. Additionally one should (integer) divide k by b in the loop, 
  34. (i.e. k = k div b) after the computation of i.
  35. >Which Karr also points out in a later post.
  36.  
  37. Follows is a quickly written C++ program for this, that has been tested
  38. to be correct for all permutations up to rank 7:
  39.  
  40. ===============================================================================
  41.  
  42. //permute.C,  a C++ program for computing random permutations
  43.  
  44. #include <stream.h>
  45.  
  46. void permute( int rank, int index, int output[] ) {
  47. // returns a permutation of given rank.  
  48. // index is a number between 1 and rank!, corresponding to a unique
  49. // permutation to return
  50.  
  51.   int i;
  52.   int v[rank];
  53.   for (i = 0; i<rank;) 
  54.     v[i] = ++i;
  55.  
  56.   int t = rank-1;
  57.   int p = 0;
  58.  
  59.   for (int b = rank; b>1; b--) {
  60.     i = index % b;
  61.       index /= b;
  62.     output[p++] = v[i]; 
  63.     v[i] = v[t--];
  64.   }
  65.   output[rank-1] = v[0];
  66. }
  67.  
  68. int fact( int v ) {
  69.   if (v>1) {
  70.     int w = v--;
  71.     for (; v > 1; v--)
  72.     w *= v;
  73.     return w;
  74.   }
  75.   else 
  76.     return 1;
  77. }
  78.  
  79. void vecset( int dest[], int source[], int rank ) {
  80. //assign dest permutation vector to be equall to source
  81. //vectors are of length rank 
  82.     for (int i =0; i<rank; i++) 
  83.       dest[i] = source[i];
  84.     //use memcpy for faster results if you like
  85. }
  86.  
  87. int is_same_vec( int v1[], int v2[], int rank ) {
  88. //return true if v1 and v2 are identical vectors of length rank
  89.     for (int i = 0; i<rank; i++)
  90.       if (v1[i] != v2[i]) return 0;
  91.     return 1;
  92. }
  93.  
  94. void display( int v1[], int rank ) {
  95. //display a permutation vector on standard output
  96.     for (int i = 0; i<rank; i++) 
  97.          cout << v1[i];
  98.       cout << "\n";
  99. }
  100.  
  101. main( int argc, char * argv[] ) {
  102. //generate and display permutation vectors, 
  103.  
  104.   for (int rank = 1; rank < 7; rank++) {
  105.     cout << "\n";  //new line
  106.     int output [rank];  // a particular permutation
  107.     int savoutput[fact(rank)] [rank]; //save all permutation vectors 
  108.  
  109.     //generate and display all permutation vectors of given rank
  110.     for (int k = fact(rank); k>0; k--) {
  111.     permute( rank, k, output );
  112.     vecset(savoutput[k-1], output, rank);
  113.     display( output, rank );
  114.     }
  115.  
  116.     //test uniqueness of permutation vectors of given rank
  117.     for (int j = 0; j<fact(rank)-1; j++)
  118.       for (int n = j+1; n<fact(rank); n++)
  119.     if (is_same_vec(savoutput[j], savoutput [n], rank)) {
  120.         cout << "error " << n << " " << j 
  121.         << " rank= " << rank << "\n";
  122.         display( savoutput[j], rank );
  123.         display( savoutput[n], rank );
  124.     }
  125.  
  126.   }
  127. }
  128.