Velocity Reviews > Looping question

# Looping question

Robocop
Guest
Posts: n/a

 10-23-2008
Having just started using C again after some years off, i've been
stumped by a problem i think someone more experienced could probably
solve pretty easily. I have these 4 objects (vectors), and i want to
find a combination of these 4 objects into two pairs, where the sum of
a specific attribute of each vector in each pair comes closest to some
base value. So all i want to do is run through the permutations of
these 4 objects and find the combination that results in two pairs
looking as close as possible to some base value.

The only thing i could think of creating a temporary vector,
initiating it by just dumping in one permutation, then looping over my
vector with the 4 objects in it, doing different permutations,
comparing those to the values in the temporary vector, and if this
permutation is better, pushing back the current pair values into the
temporary vector. After all the looping is done, i would just use the
temporary vector as my best fits.

Could anyone think of a possible solution that is simpler? I'm
currently trying to implement this solution but it's not quite
working. Any comments would be greatly appreciated.

Andrea Taverna
Guest
Posts: n/a

 10-23-2008
I suppose the pairs are unordered, i.e. that the optimality of the pair
doesn't depend on the order in which its components are put. And that
the left component of the pair has to be different from the right one.
Under this condition, you just need to look at S(S-1)/2 pairs, where S is
the number of objects.

If it is so, you should define an order between pairs, to avoid
repetition. To do so, you just need to use the objects' indexes inside
the vector.
Moreover you could avoid copying between vectors, at least during search,
by representing the optimal pair as a struct <v_best,best_i,best_j> where
v_best is the sum of attributes and best_i, best_j the indexes, inside
the vector of objects, of the left and right components respectively.

The search loop would then look like this:
for (i = 0; i < S; i++)
for (j = i + 1; j < S; j++)
{
v_temp = getPairValue(objects[i],objects[j]);
if ( fabs(v_temp - base) < fabs(v_best - base)) // fabs
= absolute value
{
v_best = v_temp;
i_best = i; j_best = j;
};
};

Hope I understood you correctly.

regards

Andrea