∑ Back to Java Tutorial.

Java Tutorial: Partition by Equivalence

20050219, Heavy 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 depending on your fluency in Java. See comment at the bottom for a Java version's input/output spec.

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

#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;
}

For the java version, merge would be a static function. The input would 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 criteria. 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, append at the bottom these lines:

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

Then, in Terminal, type “perl t.pl” to run it. It will print out the result. (provided you have Perl installed on your system. It is in Mac OS X 10.3 by default.)

↓

to be posted

For the same code in Python, see http://xahlee.org/perl-python/partition_by_equiv.html

∑ Back to Java Tutorial.
Page created: 2005-01.
© 2005 by Xah Lee.
Xah Signet