in reply to Re^2: Gift Exchange Code
in thread Gift Exchange Code

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).


Replies are listed 'Best First'.
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.

      Sure it does. I guess I need to state an assumption - lisp-like lexicals (variables are unmodified by calls that receive them).

      p0 = (A, B, C, D); Call match(p0) x1 <= A; p1 = (B, C, D); p.pop x1 <= A; y1 <= B; valid pair, call match(C,D) x2 <= C; p2 = (D); p.pop x2 <= C; y2 <= D; invalid pair - return FAIL x1 <= A; y1 <= C; valid pair, call match(B,D) x2 <= B; p2 = (D); p.pop x2 <= B; y2 <= D; valid pair, call match() p3 = () p3.empty - return SUCCESS r <= ((B, D)); Push results - return SUCCESS r <= ((B, D), (A, C)) Push results - return SUCCESS SUCCESS Results are B&D, A&C

      Now, I will give you that the results will be the same every time, and perhaps it would be good to randomize the list every time match is called to try to mix up the results here.

      I will also give you that if D could only match with A that this would return FAIL, but if there are pairings to be had, this should find them. Perhaps not the most efficiently, but it should find them.

      If I were to implement it in lisp, or even Perl, I would probably return a (STATUS, results) pair, but that is an implementation detail and doesn't really change the algorithm.

      Please help me find where I am missing the mistake in the algorithm.