-
Notifications
You must be signed in to change notification settings - Fork 20
/
combn.f
159 lines (134 loc) · 4.2 KB
/
combn.f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
SUBROUTINE sla_COMBN ( NSEL, NCAND, LIST, J )
*+
* - - - - - -
* C O M B N
* - - - - - -
*
* Generate the next combination, a subset of a specified size chosen
* from a specified number of items.
*
* Given:
* NSEL i number of items (subset size)
* NCAND i number of candidates (set size)
*
* Given and returned:
* LIST i(NSEL) latest combination, LIST(1)=0 to initialize
*
* Returned:
* J i status: -1 = illegal NSEL or NCAND
* 0 = OK
* +1 = no more combinations available
*
* Notes:
*
* 1) NSEL and NCAND must both be at least 1, and NSEL must be less
* than or equal to NCAND.
*
* 2) This routine returns, in the LIST array, a subset of NSEL integers
* chosen from the range 1 to NCAND inclusive, in ascending order.
* Before calling the routine for the first time, the caller must set
* the first element of the LIST array to zero (any value less than 1
* will do) to cause initialization.
*
* 2) The first combination to be generated is:
*
* LIST(1)=1, LIST(2)=2, ..., LIST(NSEL)=NSEL
*
* This is also the combination returned for the "finished" (J=1)
* case.
*
* The final permutation to be generated is:
*
* LIST(1)=NCAND, LIST(2)=NCAND-1, ..., LIST(NSEL)=NCAND-NSEL+1
*
* 3) If the "finished" (J=1) status is ignored, the routine
* continues to deliver combinations, the pattern repeating
* every NCAND!/(NSEL!*(NCAND-NSEL)!) calls.
*
* 4) The algorithm is by R.F.Warren-Smith (private communication).
*
* P.T.Wallace Starlink 25 August 1999
*
* Copyright (C) 1999 Rutherford Appleton Laboratory
*
* License:
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program (see SLA_CONDITIONS); if not, write to the
* Free Software Foundation, Inc., 59 Temple Place, Suite 330,
* Boston, MA 02111-1307 USA
*
*-
IMPLICIT NONE
INTEGER NSEL,NCAND,LIST(NSEL),J
INTEGER I,LISTI,NMAX,M
LOGICAL MORE
* Validate, and set status.
IF (NSEL.LT.1.OR.NCAND.LT.1.OR.NSEL.GT.NCAND) THEN
J = -1
GO TO 9999
ELSE
J = 0
END IF
* Just starting?
IF (LIST(1).LT.1) THEN
* Yes: return 1,2,3...
DO I=1,NSEL
LIST(I) = I
END DO
ELSE
* No: find the first selection that we can increment.
* Start with the first list item.
I = 1
* Loop.
MORE = .TRUE.
DO WHILE (MORE)
* Current list item.
LISTI = LIST(I)
* Is this the final list item?
IF (I.GE.NSEL) THEN
* Yes: comparison value is number of candidates plus one.
NMAX = NCAND+1
ELSE
* No: comparison value is next list item.
NMAX = LIST(I+1)
END IF
* Can the current item be incremented?
IF (NMAX-LISTI.GT.1) THEN
* Yes: increment it.
LIST(I) = LISTI+1
* Reinitialize the preceding items.
DO M=1,I-1
LIST(M) = M
END DO
* Break.
MORE = .FALSE.
ELSE
* Can't increment the current item: is it the final one?
IF (I.GE.NSEL) THEN
* Yes: set the status.
J = 1
* Restart the sequence.
DO I=1,NSEL
LIST(I) = I
END DO
* Break.
MORE = .FALSE.
ELSE
* No: next list item.
I = I+1
END IF
END IF
END DO
END IF
9999 CONTINUE
END