source: trunk/MagicSoft/slalib/permut.c@ 8462

Last change on this file since 8462 was 731, checked in by tbretz, 25 years ago
*** empty log message ***
  • Property svn:executable set to *
File size: 3.8 KB
Line 
1#include "slalib.h"
2#include "slamac.h"
3void 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}
Note: See TracBrowser for help on using the repository browser.