home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 2 / RISC_DISC_2.iso / pd_share / program / language / bob / !ArmBob / progs / Permute < prev   
Encoding:
Text File  |  1995-01-11  |  1.6 KB  |  96 lines
  1. /* permutations      GCW      11/01/95   
  2.  
  3.    This uses and displays the following algorithm for
  4.    running through permutations from 0 2 ... n to
  5.    n ... 1 0.  
  6.    Step 1. Starting from the right hand end, find the
  7.            first element smaller than its right hand 
  8.            neighbour - call it fred. Then find the
  9.            next largest number to the right of fred,
  10.            call it sam.
  11.    Step 2. Swap fred and sam.
  12.    Step 3. Reverse the list of numbers to the right
  13.            of fred's old position.
  14.  
  15.   This program shows the intermediate steps, underlining
  16.   the pair (fred,sam).
  17. */
  18.  
  19.  
  20. main()
  21. {
  22.  do
  23.  {
  24.   print("Input a smallish number (2-7): ");
  25.   n = val(input());
  26.  } 
  27.  until (n < 8 && n > 1);
  28.  v = newvector(n);
  29.  fact = 1;
  30.  for ( k = n; k > 0;)
  31.  {
  32.   fact *= k--;
  33.   v[k] = k;
  34.  }
  35.  print("> ");
  36.  display(v);
  37.  newline();
  38.  for (k = 1; k < fact; k++)
  39.   permute(v);
  40. }
  41.  
  42. display(v)
  43. {
  44.  local i,n;
  45.  n = sizeof(v);
  46.  for ( i = 0; i < n; i++)
  47.   print(v[i]," ");
  48. }
  49.  
  50. newline()
  51. { print("\n"); }
  52.  
  53. permute(v)
  54. {
  55.  local n,fred,sam;
  56.  n = sizeof(v);
  57.  sam = n-1;
  58.  fred = sam-1;
  59.  while (v[fred] > v[fred+1] && fred > 0) fred--;
  60.  while (v[sam] < v[fred] && sam > fred) sam--;
  61.  underline(fred,sam,n);
  62.  swap(v,fred,sam);
  63.  display(v);
  64.  reverse(v,fred+1);
  65.  print("    reverse\n> ");
  66.  display(v);
  67.  newline();
  68. }
  69.  
  70. reverse(v,k)
  71. {
  72.  local n,i,half,offset;
  73.  n = sizeof(v);
  74.  half = (n+k)/2;
  75.  offset = n+k-1;
  76.  for (i = k; i < half; i++)
  77.    swap(v,i,offset-i);
  78. }
  79.  
  80. swap(v,i,j)
  81. {
  82.  local w;
  83.  w = v[i];
  84.  v[i] = v[j];
  85.  v[j] = w;
  86. }
  87.  
  88. underline(i,j,n)
  89. {
  90.  local k;
  91.  print("  ");
  92.  for(k = 0; k < n; k++)
  93.     print(((k == i)||(k == j))?"^ ":"  ");
  94.  print("    swap\n  ");
  95. }
  96.