|laziness, impatience, and hubris|
Re^4: Possible pairings for first knockout round of UEFA champions leagueby LanX (Canon)
|on Dec 22, 2012 at 20:54 UTC||Need Help??|
The algorithm constructs recursively possible combinations of runner-ups meeting an ordered set of group winners:
now if you take a look at this excerpt of the results and you will notice that the last 4 branches are repeating.
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.