|
From: | Chris Marks |
Subject: | Re: Recursive find of set of maximum numbers |
Date: | Thu, 20 Oct 2011 15:20:39 -0400 |
I have a vector of integers sorted in descending order. I need to extract the
indexes of the maximum sum of N values, then the next maximum sum etc.
For example, there are 10 integers a(1) to a(10), where a(1) is the largest
number and a(10) is the smallest. Let's say N=3. The first max sum would
give me the obvious vector of (1,2,3) then the next max sum would give me
(1,2,4). But the next max sum vector could be (1,2,5) or (2,3,4) depending
on the values in a(). If a is (10000,10,9,8,7...) then (1,2,5) is the
resulting vector but if a is (100,90,80,70,10...) then (2,3,4) is the
result. The very last vector to be returned would be (8,9,10).
Is there a built-in function that would cut down the processing time of this
algorithm?
Thanks.
>>> X=-1*sort(round(-100*rand([8 1])))
X =
100
77
72
67
48
42
33
17
>>> C=combs([1:8],3)'
C =
Columns 1 through 20:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 5 5 5 6 6
3 4 5 6 7 8 4 5 6 7 8 5 6 7 8 6 7 8 7 8
Columns 21 through 40:
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3
7 3 3 3 3 3 4 4 4 4 5 5 5 6 6 7 4 4 4 4
8 4 5 6 7 8 5 6 7 8 6 7 8 7 8 8 5 6 7 8
Columns 41 through 56:
3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 6
5 5 5 6 6 7 5 5 5 6 6 7 6 6 7 7
6 7 8 7 8 8 6 7 8 7 8 8 7 8 8 8
>>> S=sum(X(C))
S =
Columns 1 through 13:
249 244 225 219 210 194 239 220 214 205 189 215 209
Columns 14 through 26:
200 184 190 181 165 175 159 150 216 197 191 182 166
Columns 27 through 39:
192 186 177 161 167 158 142 152 136 127 187 181 172
Columns 40 through 52:
156 162 153 137 147 131 122 157 148 132 142 126 117
Columns 53 through 56:
123 107 98 92
>>> [Ss, idx] = sort(S)
Ss =
Columns 1 through 13:
92 98 107 117 122 123 126 127 131 132 136 137 142
Columns 14 through 26:
142 147 148 150 152 153 156 157 158 159 161 162 165
Columns 27 through 39:
166 167 172 175 177 181 181 182 184 186 187 189 190
Columns 40 through 52:
191 192 194 197 200 205 209 210 214 215 216 219 220
Columns 53 through 56:
225 239 244 249
idx =
Columns 1 through 16:
56 55 54 52 46 53 51 36 45 49 35 43 33 50 44 48
Columns 17 through 32:
21 34 42 40 47 32 20 30 41 18 26 31 39 19 29 17
Columns 33 through 48:
38 25 15 28 37 11 16 24 27 6 23 14 10 13 5 9
Columns 49 through 56:
12 22 4 8 3 7 2 1
>>> Cs=C(:,idx);
>>> N=[Cs; Ss];
>>> N=N(:,56:-1:1)';
N =
1 2 3 249
1 2 4 244
1 3 4 239
1 2 5 225
1 3 5 220
1 2 6 219
2 3 4 216
1 4 5 215
1 3 6 214
1 2 7 210
1 4 6 209
1 3 7 205
1 4 7 200
2 3 5 197
1 2 8 194
2 4 5 192
2 3 6 191
1 5 6 190
1 3 8 189
3 4 5 187
2 4 6 186
1 4 8 184
2 3 7 182
3 4 6 181
1 5 7 181
2 4 7 177
1 6 7 175
3 4 7 172
2 5 6 167
2 3 8 166
1 5 8 165
3 5 6 162
2 4 8 161
1 6 8 159
2 5 7 158
4 5 6 157
3 4 8 156
3 5 7 153
2 6 7 152
1 7 8 150
4 5 7 148
3 6 7 147
4 6 7 142
2 5 8 142
3 5 8 137
2 6 8 136
4 5 8 132
3 6 8 131
2 7 8 127
4 6 8 126
5 6 7 123
3 7 8 122
4 7 8 117
5 6 8 107
5 7 8 98
6 7 8 92
[Prev in Thread] | Current Thread | [Next in Thread] |