[perl-python] generic equivalence partition

[Bryan]

Xah Lee wrote:
> another functional exercise with lists.
> 
> Here's the perl documentation. I'll post a perl and the translated
> python version in 48 hours.
> 
> =pod
> 
> 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.)
> 
> 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']];
> 
> =cut
> 
> 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. For example, 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.
> 
>  Xah
>  xah at xahlee.org
>  http://xahlee.org/PageTwo_dir/more.html
> 

this is the first thing that came to my mind.  i'm sure there are more clever 
ways to do this.

elements = [['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']]
pos = {}

for i, element in enumerate(elements):
     pos.setdefault(element[-1], []).append(i+1)

p = pos.values()
p.sort()
[[1], [2, 3, 4], [5], [6], [7, 8]]


bryan