Home Original page

[perl-python] generic equivalence partition

David Eppstein eppstein at ics.uci.edu
Thu Feb 24 23:59:48 EST 2005 
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/
More information about the Python-list mailing list