Algorithm::Pair::Best 1.010

Algorithm::Pair::Best is a Perl module to select pairings (designed for Go tournaments, but can be used for anything, really).

SYNOPSIS

use Algorithm::Pair::Best;

my $pair = Algorithm::Pair::Best->new( ? options ? );

$pair->add( item, ? item, ... ? );

@pairList = $pair->pick( ? $window ? );

After creating an Algorithm::Pair::Best->new object, add a list of items (players) to be paired. add connects the new items into a linked list. The linked list must consist of an even number of items or youll get an error when you try to pick the pairs.

Pairings are determined partially by the original order items were added, but more importantly, items are paired based on scores which are determined by an info hash used to attach any random data to the item, and user supplied functions to provide a score for each item in relation to other items. It may be convenient to add access methods to the Algorithm::Pair::Best package from the main namespace (see the scoreSubs option to new below for an example).
Algorithm::Pair::Best->pick explores all combinations of items and returns the pairing with the best (highest) score. This can be an expensive proposition - the number of combinations goes up very fast with respect to the number of items:

items combinations
2 1 (1)
4 3 (1 * 3)
6 15 (1 * 3 * 5)
8 105 (1 * 3 * 5 * 7)
10 945 (1 * 3 * 5 * 7 * 9
12 10395 (1 * 3 * 5 * 7 * 9 * 11)
14 135135 (1 * 3 * 5 * 7 * 9 * 11 * 13)

It is clearly unreasonable to try to pair a significant number of items. On my system it takes about 2 seconds to pair 12 items (6 pairs), and 20 seconds to pair 14 items (with no negative scores only optimization). Trying to completely pair even 30 items would take too long.

Fortunately, there is a way to get pretty good results for large numbers, even if theyre not perfect. Instead of trying to pair the whole list at once, Algorithm::Pair::Best->pick pairs a series of smaller groups to get good local results. The new method accepts a window option to limit the number of pairs in each window. The window option can also be overridden by calling pick with an explicit window argument:

$pair->pick($window);

See the description of the window option below.