generic equivalence partition

[Xah Lee]

# the following solution is submitted by
# Sean Gugler and David Eppstein independently
# 20050224.

@def parti(aList, equalFunc):
@    result = []
@    for i in range(len(aList)):
@        for s in result:
@            if equalFunc( aList[i], aList[s[0]] ):
@                s.append(i)
@                break
@        else:
@            result.append( [i] )
@    return [[x+1 for x in L] for L in result] # add 1 to all numbers
@
@---------------

as for my original perl code, i realized it is written to work on a
sorted input. Here it is and the translated Python code.

# perl
sub parti($$) {
my @li = @{$_[0]};
my $sameQ = $_[1];

my @tray=(1);
my @result;

for (my $i=1; $i <= ((scalar @li)-1); $i++) {
  if (&$sameQ($li[$i-1], $li[$i])) {
    push @tray, $i+1}
  else {
    push @result, [@tray]; @tray=($i+1);
  }
}
push @result, [@tray];
return \@result;
}


@#python
@def parti(li,sameQ):
@    tray=[1];
@    result=[];
@
@    for i in range(1, len(li) ):
@        if sameQ(li[i-1],li[i]):
@            tray.append(i+1)
@        else:
@            result.append(tray)
@            tray=[i+1]
@    result.append(tray)
@    return result
@

http://xahlee.org/perl-python/gen_parti_by_equiv.html

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