algorithmic problem...

[gregorynoob]

okay so i've got n and an array of n numbers, i have to go through all the three's of numbers like a, a[j], a[k] so that i < j < k and take the maximum of each such numbers (max of a, a[j], a[k]). my first guess is three loops but that seems to be to slow:

for( int i = 0; i < n-2; ++i )
       for( int j = i+1; j < n-1; ++j )
              for( int k = j+1; k < n; ++k )
                   s += max( a[i], max( a[j], a[k] ) );

[Alex Edwards]

Does n have to be a factor of 3, or is n just some arbitrary number?

[invisal]

Please explain it more clearly. I don't seem to understand what are you trying to do.

[gregorynoob]

hmm... well ok
you get n numbers, where n is in N...
you gotta find all sets of 3 numbers so that the index of first is less than the second and the second is less than the third... you gotta sum the max elements of the sets of three.

[Sky Diploma]

Hey, I dont seem to see any other method than this one. Is there anything wrong with the solution ?

[gregorynoob]

umm, it's slow

[Alex Edwards]

You know, I tried to make up for my dumb response earlier by developing a meta-program for this algorithm to see if it would speed it up some.

I spent the last 2.5 hours doing tests on the std max, a macro max and my own definition of max. None worked so I thought that resorting to a templatized enumerated result would be more efficient but I can't spend more time on this at the moment.

[vijayan121]

any 3-combination of the N-set would consist of numbers at 3 different positions in the array; you could choose positions i,j,k out of these three such that i<j<k holds.

so doesn't the problem reduce to generating all unique 3-combinations of an N-set.

several algorithms to do this efficiently exist.
Chase's twiddle or Knuth's (volume4) algorithms come to mind.

additional info: http://www.theory.csc.uvic.ca/~cos/inf/comb/CombinationsInfo.html

[VernonDozier]

I don't know how to use the math BBCode, so this post won't look as good as it could, but focus on the concept. I'm going to just use (n choose m) to denote the statistical combinations

Consider a list of 5 numbers: 3 5 7 8 9 So n = 5 here. We're dealing with groups of 3 here, so let's make a varaible called m to denote that. m = 3. Notice the numbers are in order here. If your a matrix is something like this: 7 5 3 9 8 sort it so it's in order, and remember n = 5 and m = 3 (denoting number of elements and the fact that we're dealing in groups of 3). 3 5 7 8 9 Consider that in a group of three numbers, 9 will be the maximum of any triplet it is in. How many triplets is 9 in? Answer: The number of ways you can pick the two numbers from the remaining 4 elements after you've picked 9, or (n - 1 choose m - 1) or (4 choose 2). So the sum of the maximums when 9 is one of the elements in the triplet is: 9 * (4 choose 2) = 9 * 6 = 54 Now look at the triplets where 9 isn't one of the members. We have 4 numbers left: 3 5 7 8 8 is the maximum of any triple it is in here. How many times is 8 in a triplet here? Pick 8 and you have to pick 2 numbers from the 3 remaining numbers (3 5 7). How many ways can you do that? (3 choose 2). So the sum of the remaining maximums where 8 is a member of the triplet is: 8 * (3 choose 2) = 8 * 3 = 24 Finally, let's look at the triplets where neither 8 nor 9 is a member of the triplet. the remaining numbers are (3 5 7). How many triplets can you make from this? Answer: (3 choose 3), or 1. What's the maximum of (3 5 7)? 7. So you get:

7 * (3 choose 3) = 7 * 1 = 7

So you end up with 54 + 24 + 7 = 85, which is the same as you get when you do it with you program:

#include <iostream>
#include <algorithm>
using namespace std;

int main ()
{
    int s = 0;
    int a[] = {3, 5, 7, 8, 9};
    int n = 5;
    
    for( int i = 0; i < n-2; ++i )
       for( int j = i+1; j < n-1; ++j )
              for( int k = j+1; k < n; ++k )
                   s += max( a[i], max( a[j], a[k] ) );
                   
    cout << s << endl;
    return 0;
}

It'll be faster because you don't have as many for-loops and comparisons. Sort it first, then just do a single loop counting down from n to k (5 to 3 in this case).

Hope this helps.

EDIT - Whoops! I mean count down from n to m. m represents the number of elements in the group (3 in this case), not k. I forgot which variable I had defined.

[gregorynoob]

wow, thanks for help all, and i was thinking about getting Knuth's books, i've already got Sedgewick's but don't know should i buy those too. i've seen 3 volumes selling in a set, i checked it out, seems to be full of high-level math, anyone knows if i should get those?
i was thinking about Cormen's introduction to algorithms too...cause Sedgewick's too lazy to gief me strings.