| 1 | #include "slalib.h"
|
|---|
| 2 | #include "slamac.h"
|
|---|
| 3 | void slaPermut ( int n, int istate[], int iorder[], int* j )
|
|---|
| 4 | /*
|
|---|
| 5 | ** - - - - - - - - - -
|
|---|
| 6 | ** s l a P e r m u t
|
|---|
| 7 | ** - - - - - - - - - -
|
|---|
| 8 | **
|
|---|
| 9 | ** Generate the next permutation of a specified number of items.
|
|---|
| 10 | **
|
|---|
| 11 | ** Given:
|
|---|
| 12 | ** n int number of items: there will be n! permutations
|
|---|
| 13 | **
|
|---|
| 14 | ** Given and Returned:
|
|---|
| 15 | ** istate int[n] state, istate[0]=-1 to initialize
|
|---|
| 16 | **
|
|---|
| 17 | ** Returned:
|
|---|
| 18 | ** istate int[n] state, updated ready for next time
|
|---|
| 19 | ** iorder int[n) next permutation of numbers 1,2,...,n
|
|---|
| 20 | ** *j int status: -1 = illegal n (zero or less is illegal)
|
|---|
| 21 | ** 0 = OK
|
|---|
| 22 | ** +1 = no more permutations available
|
|---|
| 23 | **
|
|---|
| 24 | ** Notes:
|
|---|
| 25 | **
|
|---|
| 26 | ** 1) This routine returns, in the iorder array, the integers 1 to n
|
|---|
| 27 | ** inclusive, in an order that depends on the current contents of
|
|---|
| 28 | ** the istate array. Before calling the routine for the first
|
|---|
| 29 | ** time, the caller must set the first element of the istate array
|
|---|
| 30 | ** to -1 (any negative number will do) to cause the istate array
|
|---|
| 31 | ** to be fully initialized.
|
|---|
| 32 | **
|
|---|
| 33 | ** 2) The first permutation to be generated is:
|
|---|
| 34 | **
|
|---|
| 35 | ** iorder[0]=n, iorder[1]=n-1, ..., iorder[n-1]=1
|
|---|
| 36 | **
|
|---|
| 37 | ** This is also the permutation returned for the "finished"
|
|---|
| 38 | ** (j=1) case.
|
|---|
| 39 | **
|
|---|
| 40 | ** The final permutation to be generated is:
|
|---|
| 41 | **
|
|---|
| 42 | ** iorder[0]=1, iorder[1]=2, ..., iorder[n-1]=n
|
|---|
| 43 | **
|
|---|
| 44 | ** 3) If the "finished" (j=1) status is ignored, the routine continues
|
|---|
| 45 | ** to deliver permutations, the pattern repeating every n! calls.
|
|---|
| 46 | **
|
|---|
| 47 | ** Last revision: 14 July 1999
|
|---|
| 48 | **
|
|---|
| 49 | ** Copyright P.T.Wallace. All rights reserved.
|
|---|
| 50 | */
|
|---|
| 51 | {
|
|---|
| 52 | int i, ip1, islot, iskip;
|
|---|
| 53 |
|
|---|
| 54 |
|
|---|
| 55 | /* ------------- */
|
|---|
| 56 | /* Preliminaries */
|
|---|
| 57 | /* ------------- */
|
|---|
| 58 |
|
|---|
| 59 | /* Validate, and set status. */
|
|---|
| 60 | if ( n < 1 ) {
|
|---|
| 61 | *j = -1;
|
|---|
| 62 | return;
|
|---|
| 63 | } else {
|
|---|
| 64 | *j = 0;
|
|---|
| 65 | }
|
|---|
| 66 |
|
|---|
| 67 | /* If just starting, initialize state array */
|
|---|
| 68 | if ( istate[0] < 0 ) {
|
|---|
| 69 | istate[0] = -1;
|
|---|
| 70 | for ( i = 1; i < n; i++ ) {
|
|---|
| 71 | istate[i] = 0;
|
|---|
| 72 | }
|
|---|
| 73 | }
|
|---|
| 74 |
|
|---|
| 75 | /* -------------------------- */
|
|---|
| 76 | /* Increment the state number */
|
|---|
| 77 | /* -------------------------- */
|
|---|
| 78 |
|
|---|
| 79 | /* The state number, maintained in the istate array, is a mixed-radix */
|
|---|
| 80 | /* number with n! states. The least significant digit, with a radix of */
|
|---|
| 81 | /* 1, is in istate[0]. The next digit, in istate[1], has a radix of 2, */
|
|---|
| 82 | /* and so on. */
|
|---|
| 83 |
|
|---|
| 84 | /* Increment the least-significant digit of the state number. */
|
|---|
| 85 | istate[0]++;
|
|---|
| 86 |
|
|---|
| 87 | /* Digit by digit starting with the least significant. */
|
|---|
| 88 | for ( i = 0; i < n; i++ ) {
|
|---|
| 89 | ip1 = i + 1;
|
|---|
| 90 |
|
|---|
| 91 | /* Carry? */
|
|---|
| 92 | if ( istate[i] >= ip1 ) {
|
|---|
| 93 |
|
|---|
| 94 | /* Yes: reset the current digit. */
|
|---|
| 95 | istate[i] = 0;
|
|---|
| 96 |
|
|---|
| 97 | /* Overflow? */
|
|---|
| 98 | if ( ip1 >= n ) {
|
|---|
| 99 |
|
|---|
| 100 | /* Yes: there are no more permutations. */
|
|---|
| 101 | *j = 1;
|
|---|
| 102 |
|
|---|
| 103 | } else {
|
|---|
| 104 |
|
|---|
| 105 | /* No: carry. */
|
|---|
| 106 | istate[ip1]++;
|
|---|
| 107 | }
|
|---|
| 108 | }
|
|---|
| 109 | }
|
|---|
| 110 |
|
|---|
| 111 | /* ------------------------------------------------------------------- */
|
|---|
| 112 | /* Translate the state number into the corresponding permutation order */
|
|---|
| 113 | /* ------------------------------------------------------------------- */
|
|---|
| 114 |
|
|---|
| 115 | /* Initialize the order array. All but one element will be overwritten. */
|
|---|
| 116 | for ( i = 0; i < n; i++ ) {
|
|---|
| 117 | iorder[i] = 1;
|
|---|
| 118 | }
|
|---|
| 119 |
|
|---|
| 120 | /* Look at each state number digit, starting with the most significant. */
|
|---|
| 121 | for ( i = n-1; i > 0; i-- ) {
|
|---|
| 122 |
|
|---|
| 123 | /* Initialize the position where the new number will go. */
|
|---|
| 124 | islot = -1;
|
|---|
| 125 |
|
|---|
| 126 | /* The state number digit says which unfilled slot is to be used. */
|
|---|
| 127 | for ( iskip = 0; iskip <= istate[i]; iskip++ ) {
|
|---|
| 128 |
|
|---|
| 129 | /* Increment the slot number until an unused slot is found. */
|
|---|
| 130 | islot++;
|
|---|
| 131 | while ( iorder[islot] > 1 ) {
|
|---|
| 132 | islot++;
|
|---|
| 133 | }
|
|---|
| 134 | }
|
|---|
| 135 |
|
|---|
| 136 | /* Store the number in the permutation order array. */
|
|---|
| 137 | iorder[islot] = i + 1;
|
|---|
| 138 | }
|
|---|
| 139 | }
|
|---|
