Re: Recursive find of set of maximum numbers

[Chris Marks]

On Thu, Oct 20, 2011 at 4:11 AM, thombark <address@hidden> wrote:

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.

There is probably a much more elegant way to do this, but one try follows

>>> 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