Re: [perl-python] generic equivalence partition

[Michael Spencer]

David Eppstein wrote:
In article <[EMAIL PROTECTED]>,
 "Xah Lee" <[EMAIL PROTECTED]> wrote:
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. 

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])

Unless we can inspect the predicate function and derive a hash function such 
that hash(a) == hash(b) => predicate(a,b) is True.  Then the partition can take 
linear time
i.e.,
 >>> def equal(a,b):
 ...     return a[-1] == b[-1]
 ...
 >>> def hashFunc(obj):
 ...     return hash(obj[-1])
 ...
 >>> def parti(aList, hashFunc):
 ...     eqv = {}
 ...     for i,obj in enumerate(aList):
 ...         eqv.setdefault(hashFunc(obj),[]).append(i)
 ...     return eqv.values()
 ...

In the case where the predicate is a "black box", would a logistic regression 
over a sample of inputs enable a hash function to be derived experimentally?

Michael
--
http://mail.python.org/mailman/listinfo/python-list