The algorithm constructs recursively possible combinations of runner-ups meeting an ordered set of group winners:

Paris Schalke Malaga Dortmund Turin  Bayern   Barcelona  ManU

[download]

now if you take a look at this excerpt of the results and you will notice that the last 4 branches are repeating. 

                            |
...                         |
Arsenal Porto Donezk Mailand Madrid Celtic Galatasaray Valencia
Arsenal Porto Donezk Mailand Valencia Madrid Galatasaray Celtic
Arsenal Porto Donezk Mailand Valencia Celtic Galatasaray Madrid
Arsenal Porto Donezk Mailand Celtic Madrid Galatasaray Valencia
...                         |
Arsenal Mailand Porto Donezk Madrid Celtic Galatasaray Valencia
Arsenal Mailand Porto Donezk Valencia Madrid Galatasaray Celtic
Arsenal Mailand Porto Donezk Valencia Celtic Galatasaray Madrid
Arsenal Mailand Porto Donezk Celtic Madrid Galatasaray Valencia
...                         |
                            |

[download]

Which is obviously right since the first 4 are only permutations of the same set.

So the following pairings (Turin  Bayern   Barcelona  ManU) x (Madrid Celtic Galatasaray Valencia) are always the same.

Now storing the result for a normalized representation of a already calculated set,

(something like join "-",sort(@drawn) as a hash key)

helps reusing the once calculated subresult after encountering any permutation of (Arsenal Mailand Porto Donezk)

It depends on the ratio between memory and time complexity but this normally gives an enormous boost to such search algorithms.

Cheers Rolf

In reply to Re^4: Possible pairings for first knockout round of UEFA champions league by LanX
in thread Possible pairings for first knockout round of UEFA champions league by LanX

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.