Re: Gift Exchange Code

General bin packing problem. Instead of checking if the pair of people "fit", however, you test against your own constraints - they are not SO. If not, pair them, move the pair into the bin, and move on with the remaining people.

Some pseudocode

global results = ();
function match (people) {
  if (people.empty) {
    return SUCCESS
  }
  $x = people.pop;
  foreach $y (people) {
    if (validpair($x, $y) {
      if (match(people.remove($y)) == SUCCESS) {
        results.push( {$x, $y} );
        return SUCCESS;
      }
    }
  }
  return FAILURE;
}
[download]

--MidLifeXis

Comment on Re: Gift Exchange Code Download Code

Replies are listed 'Best First'.
Re^2: Gift Exchange Code by JadeNB (Chaplain) on Oct 29, 2008 at 21:41 UTC
Maybe I misunderstand the term ‘bin packing’, but I always thought that it applied to the problem of assigning weighted objects to bins with a maximum weight allowance, in such a way that there is as little “wasted space” as possible. Aside from the general terminology of putting things in a bin, this idea doesn't seem to share anything with that problem setting. (The pseudo-code looks good for the OP's problem, though, assuming that `remove` is non-destructive.)	[reply] [d/l]
Re^3: Gift Exchange Code by MidLifeXis (Monsignor) on Oct 30, 2008 at 17:23 UTC
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	[reply] [d/l]
Re^2: Gift Exchange Code by gloryhack (Deacon) on Oct 30, 2008 at 10:26 UTC
... and if your final pair is SO so 'FAILURE'?	[reply]
Re^3: Gift Exchange Code by MidLifeXis (Monsignor) on Oct 30, 2008 at 16:43 UTC
Then the entire algorithm returns failure, since there is no possible way to match everyone into pairs successfully. This search is an exhaustive search (well, until a single successful set of matches is found). --MidLifeXis	[reply]
Re^4: Gift Exchange Code by JadeNB (Chaplain) on Oct 30, 2008 at 19:16 UTC
I think that your code is fine for the exact problem stated, but can fail in general. For example, if we have 4 people, `a`, `b`, `c`, and `d`, such that `a` can only be matched with `b` or `c`; `b` can only be matched with `a`, `c` or `d`; `c` can only be matched with `a` or `b`; and `d` can only be matched with `b`, then a matching (`a` with `c` and `b` with `d`) certainly exists, but (assuming that it searches in lexicographic order) your pseudo-code won't find it. UPDATE: Nope, I'm wrong, as MidLifeXis points out below. I forgot about the recursive check to see if deleting the candidate match would leave a ‘matchable’ collection.	[reply] [d/l] [select]
Re^5: Gift Exchange Code by MidLifeXis (Monsignor) on Oct 30, 2008 at 20:16 UTC