[perl-python] generic equivalence partition

[David Eppstein]

In article <1109245733.261643.219420 at f14g2000cwb.googlegroups.com>,
 "Xah Lee" <xah at xahlee.org> wrote:

> 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, partition by the predicate function of
> equivalence equalFunc. (a predicate function is a function that
> takes two arguments, and returns either True or False.)

In Python it is much more natural to use ranges from 0 to n-1.
In the worst case, this is going to have to take quadratic time 
(consider an equalFunc that always returns false) so we might as well do 
something really simple rather than trying to be clever.

def parti(aList,equalFunc):
    eqv = []
    for i in range(len(aList)):
        print i,eqv
        for L in eqv:
            if equalFunc(aList[i],aList[L[0]]):
                L.append(i)
                break;
        else:
            eqv.append([i])

If you really want the ranges to be 1 to n, add one to each number in 
the returned list-of-lists.

-- 
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/