[perl-python] generic equivalence partition

[Michael Spencer]

David Eppstein wrote:
> In article <1109245733.261643.219420 at f14g2000cwb.googlegroups.com>,
>  "Xah Lee" <xah at xahlee.org> 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