473,903 Members | 5,463 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

[perl-python] generic equivalence partition

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

Jul 18 '05 #1
10 2290
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
xa*@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(eleme nts):
pos.setdefault( element[-1], []).append(i+1)

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

Jul 18 '05 #2
On Thu, 24 Feb 2005 17:48:47 -0800, Bryan <be****@gmail.c om> wrote:
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.)
[snip]
example:
parti([['x','x','x','1'],
['x','x','x','2'], [snip] ['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.

[snip]


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'],

[snip] ['x', 'x', 'x', '5']]
pos = {}

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

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


Bryan: Bzzzt. Xah was proposing a GENERAL function. You have HARDWIRED
his (simplistic) example.

Xah: Bzzzt. Too close to your previous exercise.


Jul 18 '05 #3
In article <11************ **********@f14g 2000cwb.googleg roups.com>,
"Xah Lee" <xa*@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,equ alFunc):
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/
Jul 18 '05 #4
In article <ep************ *************** *@news.service. uci.edu>,
David Eppstein <ep******@ics.u ci.edu> wrote:
def parti(aList,equ alFunc):
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/
Jul 18 '05 #5
David Eppstein wrote:
In article <11************ **********@f14g 2000cwb.googleg roups.com>,
"Xah Lee" <xa*@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,equ alFunc):
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

Jul 18 '05 #6
David Eppstein <ep******@ics.u ci.edu> writes:
In article <11************ **********@f14g 2000cwb.googleg roups.com>,
"Xah Lee" <xa*@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.


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 "equivalenc e" function, much as list.sort has a "key" argument, and
itertools.group by (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.group by - sort is stable
(so doesn't alter the relative order within equivalence classes), and
groupby then picks out the equivalence classes:
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']]
# No need to sort here, as the elements are already sorted! from pprint import pprint
pprint([(k, list(v)) for k, v in groupby(element s, itemgetter(3))])

[('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
Jul 18 '05 #7
# the following solution is submitted by
# Sean Gugler and David Eppstein independently
# 20050224.

@def parti(aList, equalFunc):
@ result = []
@ for i in range(len(aList )):
@ for s in result:
@ if equalFunc( aList[i], aList[s[0]] ):
@ s.append(i)
@ break
@ else:
@ result.append( [i] )
@ return [[x+1 for x in L] for L in result] # add 1 to all numbers
@
@---------------

as for my original perl code, i realized it is written to work on a
sorted input. Here it is and the translated Python code.

# perl
sub parti($$) {
my @li = @{$_[0]};
my $sameQ = $_[1];

my @tray=(1);
my @result;

for (my $i=1; $i <= ((scalar @li)-1); $i++) {
if (&$sameQ($li[$i-1], $li[$i])) {
push @tray, $i+1}
else {
push @result, [@tray]; @tray=($i+1);
}
}
push @result, [@tray];
return \@result;
}
@#python
@def parti(li,sameQ) :
@ tray=[1];
@ result=[];
@
@ for i in range(1, len(li) ):
@ if sameQ(li[i-1],li[i]):
@ tray.append(i+1 )
@ else:
@ result.append(t ray)
@ tray=[i+1]
@ result.append(t ray)
@ return result
@

http://xahlee.org/perl-python/gen_parti_by_equiv.html

Xah
xa*@xahlee.org
http://xahlee.org/PageTwo_dir/more.html

Jul 18 '05 #8
folks:

when using google to post a reply, it sometimes truncates the subject
line. i.e. [perl-python] is lost. This software error is obvious, they
could not have not noticed it.

another thing more egregious is that google _intentionally_ edit with
people's posts. (e.g. they change email address lines without author's
permission, and they also change program codes so it no longer run).
Please spread these google irresponsibilit y to all related forums on
software responsibility and online forum issues.

Ostensible incorrect behavior like these by google is egregious enough
to generate a law suit and if such company do not take software
correctness seriously, we must punish them.

Please spread this awareness.

Xah
xa*@xahlee.org
http://xahlee.org/PageTwo_dir/more.html

Jul 18 '05 #9
People,

.... sorry for the latching on on this broadside issue, but it is
impotant ...

here's are some germane points from another online discussion:

the bug-reporting issue has came up so many times by so many people i
thought i'd make a comment of my view.

when a software is ostensibly incorrect, and if it is likely in
connection to egregious irresponsibilit y as most software companies are
thru their irresponsible licensing, the thing one should not do is to
fawn up to their ass as in filing a bug report, and that is also the
least effective in correcting the software.

the common attitude of bug-reporting is one reason that contributed to
the tremendous egregious irresponsible fuckups in computer software
industry that each of us have to endure daily all the time. (e.g.
software A clashed, software B can't do this, C can't do that, D i
don't know how to use, E download location currently broken, F i need
to join discussion group to find a work-around, G is all pretty and
dysfunctional.. . )

when a software is ostensibly incorrect and when the company is
irresponsible with their licensing, the most effective and moral
attitude is to do legal harm to the legal entity. This one an do by
filing a law suit or spreading the fact. Filing a law suit is
appropriate in severe and serious cases, and provided you have such
devotion to the cause. For most cases, we should just spread the fact.
When a company see facts flying about their incompetence or
irresponsibilit y, they will immediately mend the problem source, or
cease to exist.

Another harm sprang from the fucking bug-reporting attitude rampant
among IT morons is the multiplication of pop-ups that bug users for
bug-reporting, complete with their privacy intrusion legalese.

http://xahlee.org/UnixResource_dir/w...e_license.html

Xah
xa*@xahlee.org
http://xahlee.org/PageTwo_dir/more.html
Xah Lee wrote:
folks:

when using google to post a reply, it sometimes truncates the subject
line. i.e. [perl-python] is lost. This software error is obvious, they could not have not noticed it.

another thing more egregious is that google _intentionally_ edit with
people's posts. (e.g. they change email address lines without author's permission, and they also change program codes so it no longer run).
Please spread these google irresponsibilit y to all related forums on
software responsibility and online forum issues.

Ostensible incorrect behavior like these by google is egregious enough to generate a law suit and if such company do not take software
correctness seriously, we must punish them.

Please spread this awareness.

Xah
xa*@xahlee.org
http://xahlee.org/PageTwo_dir/more.html


Jul 18 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
8140
by: Mark Wilson CPU | last post by:
This must be easy, but I'm missing something... I want to execute a Perl script, and capture ALL its output into a PHP variable. Here are my 2 files: ------------------------------------- test3.pl ------------------------------------- print "PERL Hello from Perl! (plain print)<br>\n"; print STDERR "PERL This is text sent to STDERR<br>\n"; $output="PERL Some output:<br>\n"; for ($i=0; $i<5; $i++) {
6
5954
by: John Smith | last post by:
Hello, I have a rather odd question. My company is an all java/oracle shop. We do everything is Java... no matter what it is... parsing of text files, messaging, gui you name it. My question is this... is Perl so much better at parsing text files and outputing that we would see a substantial speed increase? We process about 10 million records in flat files a day for reformatting before putting them in a DB. Also, when it comes to...
3
3467
by: David F. Skoll | last post by:
Hi, I'm tearing my hair out on this one. I'm trying to embed a Perl interpreter into a C program. I need to be able to create and destroy the interpreter periodically, but will never actually have two interpreters at the same time. On Red Hat Linux 7.3 with Perl 5.6.1, the attached program segfaults. On Red Hat 9 with Perl 5.8.0, it works perfectly. Save the program code as "test-embed-perl.c" and the build script as "buildte". ...
0
9755
by: Kirt Loki Dankmyer | last post by:
So, I download the latest "stable" tar for perl (5.8.7) and try to compile it on the Solaris 8 (SPARC) box that I administrate. I try all sorts of different switches, but I can't get it to compile. I need it to be compiled with threads. Anyone have any wisdom on how best to do this? Here's a transcript of my latest attempt. It's long; you might want to skip to the bottom, where I try "make" and the fatal errors start happening.
13
3277
by: Otto J. Makela | last post by:
I'm trying to install to php the Perl-1.0.0.tgz package (from http://pecl.php.net/package/perl, enabling one to call perl libraries) to a pre-existing Solaris system. Unfortunately, the attempt fails in a rather dramatic way, spewing out thousands of "relocation remains"... I'm somewhat lost on what to do next, the documentation that came along with the Perl package is somewhat sparse. Anyone have suggestions? % uname -a
6
3022
by: surfivor | last post by:
I may be involved in a data migration project involving databases and creating XML feeds. Our site is PHP based, so I imagine the team might suggest PHP, but I had a look at the PHP documentation for one of the Pear modules for creating XML and it didn't look like much. I've used Perl XML:Twig and I have the impression that there is more Perl stuff available as well as the Perl stuff being well documented as I have a Perl DBI book, a Perl...
4
3720
by: billb | last post by:
I installed a perl extension for PHP to use some perl inside my php primarily because I have perl working with oracle and not php and oracle. So I want to use my old perl scripts, and use the functionality of php. The extension uses the '$perl->eval' function. i am kind of stuck with the syntax or how to put the php variable into the perl script. I have a form where the user puts in a grid reference. Then a php script that gets the...
21
34482
KevinADC
by: KevinADC | last post by:
Note: You may skip to the end of the article if all you want is the perl code. Introduction Uploading files from a local computer to a remote web server has many useful purposes, the most obvious of which is the sharing of files. For example, you upload images to a server to share them with other people over the Internet. Perl comes ready equipped for uploading files via the CGI.pm module, which has long been a core module and allows users...
0
9999
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9847
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11282
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10873
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
10500
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
8048
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7206
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
1
4726
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4308
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.