Java Exercise: Partition by Equivalence

Here's another interesting algorithmic exercise, again from part of a larger program in the previous posts.

Attached below is the original Perl documentation and its implementation. Your job today, is to write it in Java. Either by translation, or write it yourself independently from scratch. See comment at the bottom for a Java version's input/output spec.

I'll post my translation into the Java code tomorrow.

Problem Spec

#perl

=pod

merge($pairings) takes list of pairs, each pair indicates the sameness
of the two indexes. Returns a partitioned list of same indexes.

For example, if the input is
merge( [ [1,2], [2,4], [5,6] ] );

that means 1 and 2 are the same. 2 and 4 are the same. Therefore
1==2==4. The result returned is

[[4,2,1],[6,5]];

(ordering of the returned list and sublists are not specified.)

=cut

sub merge($) {
my @input = @{$_[0]};

my @interm; # array of hashs

# chop the first value of @input into @interm
$interm[0]={$input[0][0]=>'x'}; ${interm[0]}{$input[0][1]}='x'; shift
@input;

  N1: for my $aPair (@input) {
      for my $aGroup (@interm) {
          if (exists ${$aGroup}{$aPair->[0]})
{${$aGroup}{$aPair->[1]}='x'; next N1}
          if (exists ${$aGroup}{$aPair->[1]})
{${$aGroup}{$aPair->[0]}='x'; next N1}
      }
      push @interm, {$aPair->[0]=>'x'}; ${interm[-1]}{$aPair->[1]}='x';
  }

my @fin = shift @interm;

  N2: for my $group (@interm) {
      for my $newcoup (@fin) {
          foreach my $k (keys %$group) {
              if (exists ${$newcoup}{$k}) {map { ${$newcoup}{$_}='x'}
(keys %$group); next N2;}
          }
      }
      push @fin, $group;
}
return map {[keys (%$_)]} @fin;
}

Here's a spec for the java version.

“merge” should be a static function. The input should be type ArrayList, whose members are “int[]” of two slots. The return type should be ArrayList, whose members are also of type ArrayList.

PS For those of you unfamiliar with math lingoes, partition a list means to divide the given list into sublists, based on some criterions. In our case, the input list comes in the form of pairs, and its members are the union of all members in the pairs. The criterion for partition in our case is that of equivalence, specified in the pairs input.

PS to run the perl code for testing, save it as a file t.pl, and append at the bottom these lines:

use Data::Dumper;
@ss = merge( [ [1,2], [2,4], [5,6] ] );
print Dumper \@ss;

Then, type perl t.pl in terminal to run it. It will print out the result.

For the same code in Python, see: Perl Python: Partition a List by Equivalence .