[perl-python] problem: reducing comparison

[Xah Lee]

here's a interesting real-world algoritm to have fun with.

attached below is the Perl documentation that i wrote for a function
called "reduce", which is really the heart of a larger software.

The implementation is really simple, but the key is to understand what
the function should be. I'll post Perl and Python codes tomorrow for
those interested. If you are a perl programer, try to code it in
Python. (it's easy.)

This is brought to you by the Perl-Python a-day community. To
subscribe, see
http://xahlee.org/perl-python/python.html

 Xah
 xah at xahlee.org
 http://xahlee.org/PageTwo_dir/more.html

-------------------------------

=pod

e.g. reduce( $pairings, $a_pair) retured the first argument with some
pairs deleted.

Detail:

we have n things, represented by numbers 1 to n. Some of these are
identical. We want to partition the range of numbers 1 to n so that
identical ones are grouped together.

To begin comparison, we generate a list of pairings that's all
possible parings of numbers 1 to n. (of course order does not matter,
and the pairing does not contain repeations) This is the first
argument to reduce.

We'll go thru this pairings list one by one and do comparisons, remove
the pair once it has been compared. However, more pairs can be removed
if a we find a pair identical.

For example, suppose we know that 2 and 4 are identical, and if the
pairing list contains (2,3) and (4,3), one of them can be deleted
because now 2 and 4 are the same thing.

(We do this because we expect the comparison operation will be
expensive.)

reduce( $pairings, $a_pair) returns a reduced $pairings knowing that
$a_pair are identical.

The first argument $pairings must be in the form of a hash. e.g.

 {'1,5' => [1,5],'3,5' => [3,5],'2,4' => [2,4],'4,5' => [4,5],'1,3' =>
 [1,3],'2,5' => [2,5],'1,2' => [1,2],'3,4' => [3,4],'2,3' =>
 [2,3],'1,4' => [1,4]}

(Note that keys are strings of the pairs separated by a comma.)

$a_pair is a reference to a list of the form [$a,$b].

(different pairs may be deleted if the hash's pairs are given in
different order. i.e. 3,4 instead of 4,3)

The return value is a reference to a hash.

The program is deterministic but exactly which pairs are deleted is
unspecified. If the input is all possible pairs of 2 things out of n,
maximum reduction is guaranteed. 

=cut