Quick Navigator

 Search Site Miscellaneous Server Agreement Year 2038 Credits

# Manual Reference Pages  -  ALGORITHM::PAIR::BEST2 (3)

.ds Aq ’

### NAME

Algorithm::Pair::Best2 - select pairings (designed for Go tournaments, but can be used for anything).

version 2.040

### SYNOPSIS

```

use Algorithm::Pair::Best2;

my \$pair = Algorithm::Pair::Best2->new( [ options ] );

\$pair->add( item, [ item, ... ] );

@new_pairs = \$pair->pick( [ window ] );

```

### DESCRIPTION

This is a re-write of Algorithm::Pair::Best. The interface is simplified and the implementation is significantly streamlined.

After creating an Algorithm::Pair::Best2 object (with -><B>newB>), <B>addB> items to the list of items (i.e: players) to be paired. The final list must contain an even number of items or <B>pickB>ing the pairs will throw an exception.

Algorithm::Pair::Best2-><B>pickB> explores all combinations of items and returns the pairing list with the best (lowest) 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. Trying to completely pair even 30 items would take too long.

Fortunately, there is a way to get pretty good results for big lists, even if they’re not perfect. Instead of trying to pair the whole list at once, Algorithm::Pair::Best2 pairs a series of smaller groups in a sliding window to get good ’local’ results.

The <B>->newB> method accepts a <B>windowB> option to limit the number of pairs in the sliding window. The <B>windowB> option can also be overridden by calling <B>pickB> with an explicit window argument:

```

\$pair->pick(\$window);

```

The list should be at least partially sorted so that reasonable pairing candidates are within the ’sliding window’ of each other. Otherwise the final results may not be globally ’best’, but only locally good. For (e.g.) a tournament, sorting by rank is sufficient.

Here’s how a window value of 5 works: the best list for items 1 through 10 (5 pairs) is found. Save the pairing for the top two items and then slide the window down to pair items 2 through 12. Save the top pairing from this result and slide down again to items 4 through 14. Keep sliding the window down until we reach the last 10 items (which are completed in one iteration). In this way, a large number of pairings can be completed without taking factorial time.

### METHODS

 my \$pair = Algorithm::Pair::Best2->newB>( options ) Creates a newB> Algorithm::Pair::Best2 object. \$pair->addB> ( item, [ item, ...] ) Add an item (or several items) to be paired. Item(s) can be any scalar or reference. They will be passed (a pair at a time) to the scoreSubB> callback. @new_pairs = \$pair->pickB> ( ?\$window? ) Returns the best pairing found using the sliding window technique as discussed in DESCRIPTION above. windowB> is the number of pairs in the sliding window. If no windowB> argument is passed, the windowB> selected in the newB>, or the default value is used. pickB> returns the list (or a reference to the list in scalar context) of items in pairing order: new_pair[0] is paired to new_pair[1], new_pair[2] to new_pair[3], etc. If the number of items in the list (from addB>) is not even, an exception is thrown.

### OPTIONS

The <B>->newB> method accepts the following options:
<B>windowB> => number of pairs Sets the default number of pairs in the sliding window during <B>pickB>. Can also be set by passing a <B>windowB> argument to <B>pickB>.

Default: 5

<B>scoreSubB> => reference to scoring callback The callback is called as <B>scoreSubB>(item_0, item_1), where item_0 and item_1 are members of the list created by <B>addB>ing items. The callback must return a positive number representing the ’badness’ of this pairing. A good pairing should have a number closer to 0 than a worse pairing. If <B>scoreSubB> returns a negative number, an exception is thrown.

<B>scoreSubB>(A, B) should be equal to <B>scoreSubB>(B, A). <B>scoreSubB>(A, B) is called only one time (for any particular A and B), and the result is cached. <B>scoreSubB>(B, A) is never called.

Note that scores are always positive (Algorithm::Pair::Best2 searches for the lowest combined score).

Default: a subroutine that throws an exception.

<B>progressB> => reference to progress callback Each time a pair is finalized in the <B>pickB> routine, the <B>progressB>(\$item_0, \$item_1, \$idx_0, \$idx_1) callback is called where \$item_0 and \$item_1 are the most recently finalized pair, and \$idx_0, \$idx_1 are their indices in \$pair’s <B>itemsB> array:

```

progress => sub {
my (\$item_0, \$item_1, \$idx_0, \$idx_1) = @_;

my \$score = \$pair->get_score(\$idx_0, \$idx_1);   # get the score of this particular pairing
# assuming \$items have a name method that returns a string:
print \$item_0->name, " paired with ", \$item_1->name, ", score \$score\n";
},

```

Default: a subroutine that does nothing.

### METHODS

 \$pair->items Returns the array (or array ref in scaler context) of items added with addB>. \$pair->get_score( \$idx_0, \$idx_1 ) Returns the (cached) score of the pairing between the items in the itemsB> array at locations B>\$idx_0B> and B>\$idx_1B>. \$pair->scores Returns an array (or array ref in scaler context) of scores, one for each pair of items in the return array from pickB>.

### EXAMPLE

```

use Scalar::Util qw( refaddr );
use Algorithm::Pair::Best2;

my @players = (
Player->new(        # Player object defined elsewhere
name => "Player 1",
rank => 3.5,    # Player also has a rank method
),
Player->new( ... ), # more players
...
);

# some extra information not provided by Player methods:
my %already_been_paired = (
refaddr(\$player_0) => {
refaddr(\$player_1) => 1,  # player_0 played player_1
refaddr(\$player_4) => 1,  #   and player_4
},
...
);

my \$pair = Algorithm::Pair::Best2->new(
scoreSub => sub {       # score callback
my (\$player_A, \$player_B) = @_;

# Compare using the rating method defined for Players.
# Closer in rating is a better match:
my \$score = abs(\$player_A->rating - \$player_B->rating);

...

# but if they have already been matched,  increase the badness of
# this pair by a lot:
if (\$already_been_paired{refaddr(\$player_A)}{refaddr(\$player_B)}) {
\$score += 50;
}

...   # other criterion that can increase \$score

return \$score;   # always positive
}
);

\$pair->add(sort { \$a->rank <=> \$b->rank } @players);

my @pairs = \$pair->pick;

...

```

### SEE ALSO

 Games::Go::W3Gtd::Paring.pm

### AUTHOR

Reid Augustin <reid@hellosix.com>

### COPYRIGHT AND LICENSE

This software is copyright (c) 2016 by Reid Augustin.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.

Search for    or go to Top of page |  Section 3 |  Main Index

 perl v5.20.3 ALGORITHM::PAIR::BEST2 (3) 2016-03-13

Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.