source: trunk/MagicSoft/slalib/combn.c@ 9022

Last change on this file since 9022 was 731, checked in by tbretz, 25 years ago
*** empty log message ***
  • Property svn:executable set to *
File size: 3.4 KB
Line 
1#include "slalib.h"
2#include "slamac.h"
3void slaCombn ( int nsel, int ncand, int list[], int* j )
4/*
5** - - - - - - - - -
6** s l a C o m b n
7** - - - - - - - - -
8**
9** Generate the next combination, a subset of a specified size chosen
10** from a specified number of items.
11**
12** Given:
13** nsel int number of items (subset size)
14** ncand int number of candidates (set size)
15**
16** Given and Returned:
17** list int[nsel] latest combination, list[0]=0 to initialize
18**
19** Returned:
20** *j int status: -1 = illegal nsel or ncand
21** 0 = OK
22** +1 = no more combinations available
23**
24** Notes:
25**
26** 1) nsel and ncand must both be at least 1, and nsel must be less
27** than or equal to ncand.
28**
29** 2) This routine returns, in the list array, a subset of nsel integers
30** chosen from the range 1 to ncand inclusive, in ascending order.
31** Before calling the routine for the first time, the caller must set
32** the first element of the list array to zero (any value less than 1
33** will do) to cause initialization.
34**
35** 2) The first combination to be generated is:
36**
37** list[0]=1, list[1]=2, ..., list[nsel-1]=nsel
38**
39** This is also the combination returned for the "finished" (j=1)
40** case.
41**
42** The final permutation to be generated is:
43**
44** list[0]=ncand, list[1]=ncand-1, ..., list[nsel-1]=ncand-nsel+1
45**
46** 3) If the "finished" (j=1) status is ignored, the routine
47** continues to deliver combinations, the pattern repeating
48** every ncand!/(nsel!*(ncand-nsel)!) calls.
49**
50** 4) The algorithm is by R.F.Warren-Smith (private communication).
51**
52** Last revision: 25 August 1999
53**
54** Copyright P.T.Wallace. All rights reserved.
55*/
56{
57 int i, more, nmax, m;
58
59
60/* Validate, and set status. */
61 if ( nsel < 1 || ncand < 1 || nsel > ncand ) {
62 *j = -1;
63 return;
64 } else {
65 *j = 0;
66 }
67
68/* Just starting? */
69 if ( list[0] < 1 ) {
70
71 /* Yes: return 1,2,3... */
72 for ( i = 0; i < nsel; i++ ) {
73 list[i] = i+1;
74 }
75
76 } else {
77
78 /* No: find the first selection that we can increment. */
79
80 /* Start with the first list item. */
81 i = 0;
82
83 /* Loop. */
84 more = 1;
85 while ( more ) {
86
87 /* Is this the final list item? */
88 if ( i == nsel-1 ) {
89
90 /* Yes: comparison value is number of candidates plus one. */
91 nmax = ncand+1;
92
93 } else {
94
95 /* No: comparison value is next list item. */
96 nmax = list[i+1];
97 }
98
99 /* Can the current item be incremented? */
100 if ( nmax - list[i] > 1 ) {
101
102 /* Yes: increment it. */
103 list[i]++;
104
105 /* Reinitialize the preceding items. */
106 for ( m = 0; m < i; m++ ) {
107 list[m] = m+1;
108 }
109
110 /* Quit the loop. */
111 more = 0;
112
113 } else {
114
115 /* Can't increment the current item: is it the final one? */
116 if ( i == nsel-1 ) {
117
118 /* Yes: set the status. */
119 *j = 1;
120
121 /* Restart the sequence. */
122 for ( i = 0; i < nsel; i++ ) {
123 list[i] = i+1;
124 }
125
126 /* Quit the loop. */
127 more = 0;
128
129 } else {
130
131 /* No: next list item. */
132 i++;
133 }
134 }
135 }
136 }
137}
Note: See TracBrowser for help on using the repository browser.