Looping question

Discussion in 'C Programming' started by Robocop, Oct 23, 2008.

  1. Robocop

    Robocop Guest

    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.
    Robocop, Oct 23, 2008
    1. Advertisements

  2. 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,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.


    Andrea Taverna, Oct 23, 2008
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Doug
    Dec 5, 2008
  2. Pekka Niiranen
    Pekka Niiranen
    Oct 31, 2004
  3. manstey

    looping question 4 NEWB

    manstey, Jul 6, 2006, in forum: Python
    Jul 9, 2006
  4. Replies:
    Tim Chase
    Oct 3, 2006
  5. Replies:

Share This Page