You are correct. I tend to over-generalize problems. Perhaps a more proper comparison (at least from the standpoint of the algorithm) would be a knights tour problem, tic-tac-toe, or some other game-type problem.

The difference between bin-packing and this problem, is that I can assume that every item in the data set must be used. In bin packing that may not be true (bin.size < data.sum(size)).

The solutions, however, can be very similar. One area of difference that I can see is that the selection of the first item ($x = people.pop) is not correct. Perhaps removing it completely and modifying the termination check (the if clause at the top) to some fitness test (less than N% wasted space, for example) would get close enough to be a solution. Note that I did not say the best solution.

Basically I am doing a depth first search of all option paths, pruning the tree (FAILURE) if an invalid combination occurs, and building the answer as I unwind the call stack (results.push) if I exhaust the list of people (people.empty).

Now, this solution (and I don't think the original problem asked to do this) does not handle the case where there are an odd number of people in the list, and it pairs up people rather than allowing A to give to B, B to give to C, and C to give to A. Perhaps CountZero's solution would be better in this case.

--MidLifeXis

In reply to Re^3: Gift Exchange Code by MidLifeXis
in thread Gift Exchange Code by agianni

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.