Python, Perl: Partition by Equivalence

Another functional exercise with lists.

Problem Spec

Here's the Perl documentation. I'll post a Perl and the translated python version in 48 hours.

parti(aList, equalFunc)

given a list aList of n elements, we want to return a list that is a
range of numbers from 1 to n, partitioned by the predicate function of
equivalence equalFunc. (a predicate function is a function that takes
two arguments, and returns either True or False.)

Note: a mathematical aspect: there are certain mathematical constraints 
on the a function that checks equivalence. That is to say, if a==b, 
then b==a. If a==b and b==c, then a==c. And, a==a. If a equivalence 
function does not satisfy these, it is inconsistent and basically give 
meaningless result.

example:
parti([['x','x','x','1'],
['x','x','x','2'],
['x','x','x','2'],
['x','x','x','2'],
['x','x','x','3'],
['x','x','x','4'],
['x','x','x','5'],
['x','x','x','5']], sub {$_[0]->[3] == $_[1]->[3]} )

returns
  [[1],['2','3','4'],['5'],['6'],['7','8']];

In the example given, the input list's elements are lists of 4 elements, and the equivalence function is one that returns True if the last item are the same.

Note that this is a generic function. The input can be a list whose elements are of any type. What “parti” does is to return a partitioned range of numbers, that tells us which input element are equivalent to which, according to the predicate given. e.g. in the given example, it tells us that the 2nd, 3rd, 4th elements are equivalent. And they are equivalent measured by the predicate function given, which basically tests if their last item are the same integer. (note that if we want to view the result as indexes, then it is 1-based index. i.e. counting starts at 1.)

PS if you didn't realize yet, nested lists/dictionaries in Perl is a complete pain in the ass.

PS note that the code “sub {$_[0]->[3] == $_[1]->[3]}” is what's called the lambda form, in Perl.

Answers below

Python

The following solution is submitted by Sean Gugler and David Eppstein independently. 2005-02-24.

# -*- coding: utf-8 -*-
# python 2

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

Perl

It turns out that my original Perl code is written for input that has been sorted. (this implies the input set has order). Here's the original Perl code and the translated Python code:

# -*- coding: utf-8 -*-
# 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;
}

# -*- coding: utf-8 -*-
# python 2

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