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.

Replies are listed 'Best First'.
by MidLifeXis (Monsignor) on Oct 30, 2008 at 20:16 UTC

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