PERL Miscellaneous - [perl-python] generic equivalence partition

Author

[perl-python] generic equivalence partition

Xah Lee

2005-02-24, 8:57 am

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@xahlee.org
http://xahlee.org/PageTwo_dir/more.html

David Eppstein

2005-02-25, 3:58 am

In article <1109245733.261643.219420@f14g2000cwb.googlegroups.com>,
"Xah Lee" <xah@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/

David Eppstein

2005-02-25, 3:58 am

In article <eppstein-CDFABC.20594724022005@news.service.uci.edu>,
David Eppstein <eppstein@ics.uci.edu> wrote:

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

Um, take out the print, that was just there for me to debug my code.

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

Paul Moore

2005-02-26, 3:57 am

David Eppstein <eppstein@ics.uci.edu> writes:

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

As you say, with the spec as it stands, you can't do better than
quadratic time (although it's O(n*m) where m is the number of
partitions, rather than O(n^2)).

You can do a lot better if you can use a "key" function, rather than
an "equivalence" function, much as list.sort has a "key" argument, and
itertools.groupby (which is pretty close in function to this
partitioning problem) uses a key argument.

In fact, I'd have difficulty thinking of an example where I'd want a
partition function as specified, in Python. In Perl, it makes a lot of
sense, as Perl's array indexing operations lend themselves to slinging
round lists of indices like this. But in Python, I'd be far more
likely to use list.sort followed by itertools.groupby - sort is stable
(so doesn't alter the relative order within equivalence classes), and
groupby then picks out the equivalence classes:
[color=darkred]
.... ['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']]
[color=darkred]
[color=darkred]
[('1', [['x', 'x', 'x', '1']]),
('2', [['x', 'x', 'x', '2'], ['x', 'x', 'x', '2'], ['x', 'x', 'x', '2']]),
('3', [['x', 'x', 'x', '3']]),
('4', [['x', 'x', 'x', '4']]),
('5', [['x', 'x', 'x', '5'], ['x', 'x', 'x', '5']])]

If you avoid the sort, the whole thing is highly memory efficient, as
well, because by using iterators, we don't ever take a copy of the
original list.

Having cleverly redefined the question so that it fits the answer I
wanted to give, I'll shut up now :-)

Paul.
--
To attain knowledge, add things every day; to attain wisdom, remove
things every day. -- Lao-Tse

Sponsored Links