# FreeBSD Manual Pages

```Algorithm::Pair::Best2User Contributed Perl DocumentaAlgorithm::Pair::Best2(3)

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

VERSION
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 ->new), add items
to the list of items (i.e: players) to be paired.  The final list must
contain an even number of items or picking the pairs will throw an
exception.

Algorithm::Pair::Best2->pick 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 ->new method	accepts	a window option	to limit the number of pairs
in the sliding window.  The window option can also be overridden	by
calling pick 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->new( options )
Creates a new Algorithm::Pair::Best2	object.

\$pair->add ( 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
scoreSub callback.

@new_pairs = \$pair->pick	( ?\$window? )
Returns the best pairing found using	the sliding window technique
as discussed	in DESCRIPTION above.  window is the number of pairs
in the sliding window.  If no window	argument is passed, the	window
selected in the new,	or the default value is	used.

pick	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 add) is not	even, an
exception is	thrown.

OPTIONS
The ->new method	accepts	the following options:

window => number	of pairs
Sets	the default number of pairs in the sliding window during pick.
Can also be set by passing a	window argument	to pick.

Default: 5

scoreSub	=> reference to	scoring	callback
The callback	is called as scoreSub(item_0, item_1), where item_0
and item_1 are members of the list created by adding	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 scoreSub returns a	negative number, an
exception is	thrown.

scoreSub(A, B) should be equal to scoreSub(B, A).  scoreSub(A, B)
is called only one time (for	any particular A and B), and the
result is cached.  scoreSub(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.

progress	=> reference to	progress callback
Each	time a pair is finalized in the	pick routine, the
progress(\$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 items 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	add.

\$pair->get_score( \$idx_0, \$idx_1	)
Returns the (cached)	score of the pairing between the items in the
items array at locations \$idx_0 and \$idx_1.

\$pair->scores
Returns an array (or	array ref in scaler context) of	scores,	one
for each pair of items in the return	array from pick.

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.

perl v5.32.0			  2016-03-13	     Algorithm::Pair::Best2(3)
```

NAME | VERSION | SYNOPSIS | DESCRIPTION | METHODS | OPTIONS | METHODS | EXAMPLE | SEE ALSO | AUTHOR | COPYRIGHT AND LICENSE

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=Algorithm::Pair::Best2&sektion=3&manpath=FreeBSD+12.2-RELEASE+and+Ports>