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

[download]

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.

--MidLifeXis

In reply to Re^5: 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.