Trouble with search algorithm

[Kesarion]

I have an array of objects that I need to iterate through in order to get three items.

The parts of the object important in this context are: value and type.

I need to find the first three items from the array that have the greatest value sum and are of the same type.

Right now I've just used three "for" statements to iterate through the array and compare all the combinations of three items. However this is extremely inefficient and it seems like there should be a better solution. I thought sorting the array in descending order would give me the best match for the first compatible items, but that's not always true.

In the following I use a vector for the array and "compatible()" checks the type for three items:

int maxScore = 0, maxItems[3];
for(int i = 0; i < items.size() - 2; i++)
    for(int j = i + 1; j < items.size() - 1; j++)
        for(int k = j + 1; k < items.size(); k++)
            if(compatible(items[i], items[j], items[k]))
                if(maxScore < items[i].getScore() + items[j].getScore() + items[k].getScore())
                {
                    maxScore = items[i].getScore() + items[j].getScore() + items[k].getScore();
                    maxItems[0] = i; maxItems[1] = j; maxItems[2] = k;
                }
if(maxScore)
    printBestMatch(items[maxWords[0]], items[maxWords[1]], items[maxWords[2]]);
else
    cout<<"No matches found!"<<endl;

There has to be a better way of doing this.

[NathanOliver]

So you need to find some group of 3 items that has the same type and the highest sum of thier values? If that is the case then I would split you main array into seperate arrays for each type. Then sort those arrays in descending order. Then find which array has the highest sum for the first three elements.

[rubberman]

Just a style suggestion (one that will eliminate a LOT of bugs): use {} to scope ALL conditionals (if/else if/else) and loop blocks. IE:

int maxScore = 0, maxItems[3];
for(int i = 0; i < items.size() - 2; i++)
{
    for(int j = i + 1; j < items.size() - 1; j++)
    {
        for(int k = j + 1; k < items.size(); k++)
        {
            if(compatible(items[i], items[j], items[k]))
            {
                if(maxScore < items[i].getScore() + items[j].getScore() + items[k].getScore())
                {
                    maxScore = items[i].getScore() + items[j].getScore() + items[k].getScore();
                    maxItems[0] = i; maxItems[1] = j; maxItems[2] = k;
                }
            }
        }
    }
}
if(maxScore)
{
    printBestMatch(items[maxWords[0]], items[maxWords[1]], items[maxWords[2]]);
}
else
{
    cout<<"No matches found!"<<endl;
}

IE, don't be a lazy programmer! If one of my team did that (no braces), I'd rip them a new one - but then, they know better! :-)

[mike_2000_17]

NathanOliver's suggestion is reasonable:

If that is the case then I would split you main array into seperate arrays for each type. Then sort those arrays in descending order. Then find which array has the highest sum for the first three elements.

Although you can also do it all in one go, using lexicographic sorting. In other words, sort by type first and by value next, with something like this:

bool compareItems(const Item& lhs, const Item& rhs) {
  if( lhs.type() == rhs.type() )
    return lhs.value() < rhs.value();
  else
    return lhs.type() < rhs.type();
};

If you sort the entire array, it will be split in terms of types, and then in terms of values, at which point you just need to pick out the top three values of each type groups, and find the highest sum.

However, this method is a bit too heavy-duty for my taste. I would go with a much simpler method. Really, all you need to do is keep track of the top three elements for each type, so, just do that directly. Go through the array once, keeping track of those elements, and at the end, go through what you have recorded to find the highest sum. You can even keep track of the highest sum the first time around too.

[Kesarion]

Ah, I knew I shouldn't have simplified things.

Thanks for the responses everybody, they are really helpful in the case I described.

The thing is, I tried to simplify things here thinking it would make it clearer, instead it seems I've changed the problem entirely.

I used "type" to describe a more complex structure. The items are words with letters positioned on a grid. Each word has a value and my goal is to get the three words with the highest value sum with non-overlapping letters. That means "type" here has no real meaning, it's only a placeholder that I thought would simplify things. If I were to create a signature for each word it would be much more cumbersome than my current setup.

The function "compatible()" takes care of checking wether any letters overlap.

I think I've found a way using a recursive function, but I just can't get it to work, it's like my mind gets lost halfway through the process.

Let's consider a simple visual guide first:

i: 10 9 8 7 6 5 4 3 2 1
j: 10 9 8 7 6 5 4 3 2 1
k: 10 9 8 7 6 5 4 3 2 1

These are some example scores.

Now, let's consider j and k first. At first we'll have 9 + 8 = 17, then 9 + 7 = 16, 9 + 6 = 15 and at this point we realize 9 + 6 = 8 + 7 so next time if we let things go on we'll get a few sums that are less than what we're going to have in the future.

So I set up an "if" and call the recursive function for 8 and 7 before continuing. The problem is that at some point this branch will have lesser value sums than the main branch and there would have to be some mechanism to stop it. And of course a few more problems will occur that I have no idea how to counteract.

Am I going down the right path with this? Does an idea spring up in anyone's mind as to a better solution?

[Labdabeta]

Based on how you are describing your problem I think you may be facing an irreducible problem. From what I understand from your post it seems that your problem can be boiled down to this:

Find the subset of n objects from a given set with the highest value, given certain criteria for the set. Or as a function: set<object> problem(int n, int(*value)(const object &), bool(*validSet)(set<object>))

In your case n=3, objects are words with a value attached, and the criteria is that the words do not overlap.

If this indeed is your problem then I think that it is NP-Complete just because it reminds me a lot of the backpack problem. In that case the only solution will have time complexity of O(N^^n) where N is the number of objects, n is how many you want, and ^^ is two Knuth's up arrows (A^^B=A^A^A...^A B times)

As such your solution may very well be optimal for your problem (at least asymptotically).

Of course I have been wrong before too. :)

[Kesarion]

Maybe you're right Labdabeta. For now I have to make a compromise and go for second best, order the array and get the first match. It won't always be the best match, but it'll be pretty damn close. Searching through all the possible combinations takes too long.

I will continue working on that recursive function though. I finally made some headway. The code looks like a monster and I wouldn't post it here, but it's getting somewhere at least.

I would however appreciate it if anyone throws some ideas my way.