Java: Writing A Pairings Reduce Function

Here's a interesting real-world algorithm to have fun with.

Attached below is the Perl documentation for a function called “reduce”.

The implementation is really simple, but the key is to understand what the function should be. The implementation in Perl and Python is attached below. I'll post Java version tomorrow.

#perl

=pod

reduce( $pairings, $a_pair) return 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 repetitions) This is the first
argument to reduce.

Now suppose we know that 2 and 4 are identical, then we want to reduce
the pairings so that we don't have to do extra comparison. For
example, if the pairing list contains (2,3) and (4,3), one of them can
be deleted because now 2 and 4 have been determined identical.

(We do this because we expect the comparison 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 like this:

 {'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].

The return value is a reference to a hash.

=cut

sub reduce ($$) {
my %hh= %{$_[0]}; # for example: {'1,2'=>[1,2],'5,6'=>[5,6],…}
my ($j1,$j2)=($_[1]->[0],$_[1]->[1]);  # for example: [3,4]
delete $hh{"$j1,$j2"};
foreach my $k (keys %hh) {
        $k=~m/^(\d+),(\d+)$/;
        my ($k1,$k2)=($1,$2);
        if ($k1==$j1) {
            if ($j2 < $k2) {
                delete $hh{"$j2,$k2"};
            }
            else {
                delete $hh{"$k2,$j2"};
            };
        };
        if ($k2==$j1) {
            if ($k1 < $j2) {
                delete $hh{"$k1,$j2"};
            }
            else {
                delete $hh{"$j2,$k1"};
            };
        };
    }
return \%hh;
}

# Python code

def reduce(pairings, pair):
    ps=pairings.copy(); j=pair;
    ps.pop("%d,%d"%(j[0],j[1]),0)
    for k in pairings.itervalues():
        if (k[0]==j[0]):
            if (j[1] < k[1]):
                ps.pop("%d,%d"%(j[1],k[1]),0)
            else:
                ps.pop("%d,%d"%(k[1],j[1]),0)
        if (k[1]==j[0]):
            if (k[0] < j[1]):
                ps.pop("%d,%d"%(k[0],j[1]),0)
            else:
                ps.pop("%d,%d"%(j[1],k[0]),0)
    return ps

In imperative languages such as Perl and Python and Java, in general it is not safe to delete elements when looping thru a list-like entity. (it screws up the iteration) One must make a copy first, and work with the copy.

Note also that in Python there's already a function called reduce. (it is equivalent to Mathematica's Fold. Fold ) In Python, looks like user can over-ride default functions.

Here's the answer to two day ago's “pairings reduce” exercise.

import java.util.*;

public class comb {

    static HashMap combo (int n) {
        HashMap result = new HashMap(100);
        for (int j=1; j <= n; j++) {
            for (int i=1; i < j; i++) {
                int[] v= {i,j};
                result.put(i+ ","+j, v);
            }
        }
        return result;
    }

    static HashMap reduce (HashMap pairings, int[] pair) {
        int[] k= new int[2];
        int[] j= pair;
        HashMap newP = new HashMap(pairings); // make a copy to work with inside destructive loop
        newP.remove(j[0]+","+j[1]);
        for (Iterator it=pairings.values().iterator(); it.hasNext(); ){
            k = (int[]) it.next();
            if (k[0]==j[0]) {
                if (j[1] < k[1]) {
                    newP.remove(j[1]+","+k[1]);
                }
                else {
                    newP.remove(k[1]+","+j[1]);
                }
            }
            if (k[1]==j[0]) {
                if (k[0] < j[1]) {
                    newP.remove(k[0]+","+j[1]);
                }
                else {
                    newP.remove(j[1]+","+k[0]);
                }
            }
        }
        return newP;
    }

    public static void main(String[] args) {
        HashMap result = new HashMap(100);
        HashMap result2 = new HashMap(100);
        int[] pair= {2,3};
        result = combo(5);
        System.out.println(result.keySet().toString());
        System.out.println( reduce(result, pair).keySet().toString());
    }
}

The combo function is from previous exercise: Java: A Combinatorics Function

This is a direct translation from the Perl and or Python codes above.

Of interest is this line:

HashMap newP = new HashMap(pairings);

which is how one makes a copy of HashMap in Java. (with technicality, all classes that implements the Map interface can be copied this way.)

To delete a key/value pair, use the remove method:

newP.remove(j[0]+","+j[1]);

note that in Java's key-indexed pair list (For example, HashMap), the keys can be ANY Object, not just strings. In our case, the keys are strings.

Next line of interest is this:

for (Iterator it=pairings.values().iterator(); it.hasNext(); ){ … }

This is how one loop thru a list-like thing in Java.

given a list, in computing one often wants to go thru it item by item. In conventional languages this is done like this:

for (i; i >= length(myList); i=i+1) { … }

where the i is a variable used as a index, and it increases until it is equal to the number of items in the list.

In functional languages it is like this:

map( f, myList)

where the result is f applied to every item in myList. No extraneous concepts of indexing or syntax are involved.

in Object Oriented purity, one uses the concept of a Iterator object to go thru a list. A iterator object represents the elements in the list. To go to next item, use a method like next() in the iterator. For example

for (Iterator it=pairings.values().iterator(); it.hasNext(); ){ … }

the it is a Iterator object created on the fly. The pairings.value() returns a list (technically: Java “Collection” type), and the “iterator()” method turns a list into this “Iterator” object. Iterator has a grand total of 3 methods: “hasNext()”, “next()”, “remove()”. The “hasNext()” returns true if there's a next item. The “next()” returns the next item (really just return the current item, AND, move some abstract concept of a pointer to the next slot), “remove()” deletes the current item in the list the Iterator embodies.

The Iterator object has really no use outside of loops. Its existence as a object is solely a consequence of the OOP ideology. In summary, the Iterator thingy is just a complex extraneous concept and verbose syntax for doing iterations in Java.

Next line of interest is this:

k = (int[]) it.next();

The it.next() is the way to get items out of a Iterator in Java. The (int[]) there is technically called “casting”. It converts the object the Iterator returned into the type that the iterator embodies. Its existence is mandatory. Here we see another incompetence of Java. Machines clearly know the original type and can do these drudgery for us, but the Java lang won't, with all its fancy lies.

(we'll take a trip around the Java's “Interface” concept, the Abstract keyword/class, and the entire Java collections later.)