[18800] in Perl-Users-Digest
Perl-Users Digest, Issue: 968 Volume: 10
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Wed May 23 14:06:07 2001
Date: Wed, 23 May 2001 11:05:20 -0700 (PDT)
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Message-Id: <990641120-v10-i968@ruby.oce.orst.edu>
Content-Type: text
Perl-Users Digest Wed, 23 May 2001 Volume: 10 Number: 968
Today's topics:
Re: "listen" to a file <uri@sysarch.com>
ActivePerl <kay_schulz@yahoo.com>
bitwise <todd@designsouth.net>
Re: bitwise (Randal L. Schwartz)
Re: bitwise (Steven M. O'Neill)
Re: bitwise (Randal L. Schwartz)
chmod zum Datenspeichern (Andreas Schmitz)
chmod zum Datenspeichern (Andreas Schmitz)
Re: columns (Anno Siegel)
Re: foreach loop and chop problem (Peter L. Berghold)
Re: Handling JPEGs without modules <mischief@velma.motion.net>
Re: help getting data into hash from MySql nobull@mail.com
Re: Help needed - perl to download from secure website <andras@mortgagestats.com>
Re: Help needed - perl to download from secure website nobull@mail.com
Re: How to tell what version of Perl (Craig Berry)
HTML::Entities and the Mac :-( <ubl@schaffhausen.de>
Re: Mathematical Combinations (similar to "Permuting da <tom_mullenaux@agilent.com>
Re: Mathematical Combinations (similar to "Permuting da <trondmm-usenet@crusaders.no>
Re: Mathematical Combinations (similar to "Permuting da (Craig Berry)
Re: Mathematical Combinations (similar to "Permuting da (Jay Tilton)
Re: module for combinatorics? (partitions etc) (Anno Siegel)
Re: module for combinatorics? (partitions etc) (Greg Bacon)
Re: module for combinatorics? (partitions etc) <joe+usenet@sunstarsys.com>
Re: module for combinatorics? (partitions etc) <thunderbear@bigfoot.com>
Re: module for combinatorics? (partitions etc) (Abigail)
Re: module for combinatorics? (partitions etc) <thunderbear@bigfoot.com>
Re: module for combinatorics? (partitions etc) (Mark Jason Dominus)
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Wed, 23 May 2001 16:34:47 GMT
From: Uri Guttman <uri@sysarch.com>
Subject: Re: "listen" to a file
Message-Id: <x73d9w58ig.fsf@home.sysarch.com>
>>>>> "HF" == Hermann Fass <hermann@holzerath.de> writes:
HF> "Peter Søgaard" wrote:
>> Is it possible to have perl "listen to" a certain file, and then
>> trigger some event when this file is updated( i.e. overwritten ).
>> I can probably use sleep x seconds and then check the file status
>> once in a while and decide whether the file has been updated since
>> last time i checked...but is there a more correct way of doing
>> this?...if so, how? :)
HF> If you run such a status-checker as a cron-job you avoid a
HF> separate process. The latest status should go into a tmp-file
HF> (I/O overhead if you need to check very often) or in an
HF> environment-variable.
huh? an environment var?
and how does cron save process when it runs one very period you ask for?
and cron has 1 minute resolution which may be too long for the OP (who
didn't specify his problem nearly enough).
there is a tail module on CPAN and even a tail program in ppt as well as
the standard unix/gnu tail programs. many solutions to this.
uri
--
Uri Guttman --------- uri@sysarch.com ---------- http://www.sysarch.com
SYStems ARCHitecture and Stem Development ------ http://www.stemsystems.com
Learn Advanced Object Oriented Perl from Damian Conway - Boston, July 10-11
Class and Registration info: http://www.sysarch.com/perl/OOP_class.html
------------------------------
Date: Wed, 23 May 2001 18:22:56 +0200
From: Kay Schulz <kay_schulz@yahoo.com>
Subject: ActivePerl
Message-Id: <kay_schulz-DC0062.18225623052001@news.t-online.com>
Hi
unter UNIX sage ich
#!/bin/perl
wie mache ich das unter Windows 2000?
Oder geht das da gar nicht
ich kann meine Programme mit
perl Programm
aufrufen aber dass es selber startet habe ich nicht
hinbekommen
Danke
Kay
--
Kay Schulz
------------------------------
Date: Wed, 23 May 2001 15:24:38 GMT
From: "Todd Smith" <todd@designsouth.net>
Subject: bitwise
Message-Id: <WCQO6.62332$I5.13206813@news1.rdc1.tn.home.com>
Why do people usually use bitwise operations? I've never learned them
because I've never had to use them. Is there some example program that I can
write and modify so I can teach myself all the bitwise operators?
------------------------------
Date: 23 May 2001 08:32:14 -0700
From: merlyn@stonehenge.com (Randal L. Schwartz)
Subject: Re: bitwise
Message-Id: <m1bsokhyip.fsf@halfdome.holdit.com>
>>>>> "Todd" == Todd Smith <todd@designsouth.net> writes:
Todd> Why do people usually use bitwise operations? I've never learned
Todd> them because I've never had to use them. Is there some example
Todd> program that I can write and modify so I can teach myself all
Todd> the bitwise operators?
Type "bitwise" into the search box at
www.stonehenge.com/perl/googlecolumnsearch
and see which (three so far) of my (120+ so far) columns mention
that keyword.
In fact, it's probably hard to type a Perl-ish word in there that
*won't* get a hit, and if you do, and you want to see a future
column on it, please WRITE ME with the idea!
print "Just another Perl [column] hacker,"
--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<merlyn@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
------------------------------
Date: 23 May 2001 15:38:34 GMT
From: steveo@panix.com (Steven M. O'Neill)
Subject: Re: bitwise
Message-Id: <9eglhq$2c9$1@news.panix.com>
Randal L. Schwartz <merlyn@stonehenge.com> wrote:
>Type "bitwise" into the search box at
>
> www.stonehenge.com/perl/googlecolumnsearch
>
>and see which (three so far) of my (120+ so far) columns mention
>that keyword.
That's very cool. Almost too cool, though. I tried "hash references"
and got 25 pages returned. It might be useful to include the title
(and synopsis if it exists) for each of the pages too.
Regards,
Steve
--
Steven O'Neill steveo@panix.com
this is not a job-request post www.cars-suck.org
------------------------------
Date: 23 May 2001 09:03:00 -0700
From: merlyn@stonehenge.com (Randal L. Schwartz)
Subject: Re: bitwise
Message-Id: <m1eltggiiz.fsf@halfdome.holdit.com>
>>>>> "Steven" == Steven M O'Neill <steveo@panix.com> writes:
Steven> Randal L. Schwartz <merlyn@stonehenge.com> wrote:
>> Type "bitwise" into the search box at
>>
>> www.stonehenge.com/perl/googlecolumnsearch
>>
>> and see which (three so far) of my (120+ so far) columns mention
>> that keyword.
Steven> That's very cool. Almost too cool, though. I tried "hash references"
Steven> and got 25 pages returned. It might be useful to include the title
Steven> (and synopsis if it exists) for each of the pages too.
yeah, that's coming. I'm gonna take the output of google and
go fetch my local info and attach it to the link. one step at a time,
and yes, this will be a future Perl column. :) :)
print "Just another Perl hacker,"
--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<merlyn@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
------------------------------
Date: Wed, 23 May 2001 15:35:34 GMT
From: webmaster@kreativhaus-online.de (Andreas Schmitz)
Subject: chmod zum Datenspeichern
Message-Id: <3b0bd875.3155831@news.btx.dtag.de>
Hallo,
reicht ein chmod 0666 zum speichern von binarys in einem Verzeichnis
auf dem Webserver im Internet aus, oder muss ich das anders mache?
--
#!C:\perl\bin\perl.exe -wT
print map {chr(ord($_)-3)} split //, "Dqguhdv0Vfkplw}Cw0rqolqh1gh";
------------------------------
Date: Wed, 23 May 2001 15:36:21 GMT
From: webmaster@kreativhaus-online.de (Andreas Schmitz)
Subject: chmod zum Datenspeichern
Message-Id: <3b0bd8f0.3278314@news.btx.dtag.de>
Hallo,
reicht ein chmod 0666 zum speichern von binarys in einem Verzeichnis
auf dem Webserver im Internet aus, oder muss ich das anders mache?
--
#!C:\perl\bin\perl.exe -wT
print map {chr(ord($_)-3)} split //, "Dqguhdv0Vfkplw}Cw0rqolqh1gh";
------------------------------
Date: 23 May 2001 15:08:09 GMT
From: anno4000@lublin.zrz.tu-berlin.de (Anno Siegel)
Subject: Re: columns
Message-Id: <9egjop$ms0$3@mamenchi.zrz.TU-Berlin.DE>
According to Jürgen Exner <juex@my-deja.com>:
> "Willem" <smitw1@hotmail.com> wrote in message
> news:1b8ngtc02ut15ft0vij7uka2o1rt6bb28h@4ax.com...
> > I want to split records of a file into colums, and with a space
> > between the colums.
> >
> > Input from file:
> >
> 02X123593791Y103970930X123593791Y103970930X123593791Y103970930X123593791Y103
> 97093000
> > etc.
> >
> > output to file:
> > 02 X123593791 Y103970930 X123593791 Y103970930 X123593791 Y103970930
> > X123593791 Y103970930 00
>
> A simple substitute should do:
> s/\([XY]\)/ $1/g
Tempting, but it fails to isolate the final "00".
Anno
------------------------------
Date: Wed, 23 May 2001 17:32:24 GMT
From: peter@uboat.berghold.net (Peter L. Berghold)
Subject: Re: foreach loop and chop problem
Message-Id: <slrn9gnt0q.ein.peter@uboat.berghold.net>
On Wed, 23 May 2001 06:48:04 GMT,
angry_garden_salad@yahoo.com
<angry_garden_salad@yahoo.com> wrote:
[*]HI,
[*]I have the following script:
[*]#!/usr/bin/perl
[*]@hosts=`cat /u/hosts`;
[*]@lists=`cat /u/lists`;
[*]
Try:
<code>
chomp @hosts;
chomp @lists;
</code>
That might work for you better.
--
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Peter L. Berghold Peter@Berghold.Net
Schooner Technology Consulting http://www.berghold.net
Unix Professional Services Perl Perl/CGI mod_perl
------------------------------
Date: Wed, 23 May 2001 15:39:38 -0000
From: Chris Stith <mischief@velma.motion.net>
Subject: Re: Handling JPEGs without modules
Message-Id: <tgnmdqfasrrk1d@corp.supernews.com>
Eric Bohlman <ebohlman@omsdev.com> wrote:
> peter pilsl <pilsl_@goldfisch.at> wrote:
>> however: why not ftp the module-files to your host after proper compiling
>> them on your own machine and then include them using a command like
>> use lib "whatpathever"
> That will only work if your machine has the exact same architecture and OS
> as the Web host's machine, and even then only if you have the same
> compiler that the host's machine's perl was compiled with. "Solutions"
> that depend on lots of coincidences tend not to work very well.
Many ISPs and hosting companies use NetBSD, OpenBSD, Solaris, or
some Linux distro on PC-based or on Sun hardware. Most of them
either use the standard perl shipped with the OS or compile
with either the native compiler on the platform or gcc. Most
will be more than willing to tell you their hardware, OS, and
compiler specs if you ask.
So, if you know that your hardware, compiler, and OS are the same
as where your website is hosted, it's not that hard to setup the
same thing at your own office or at home (unless of course you're
a small shop and your site is hosted on an SGI box or a Sun
UltraSparc or somesuch). Since there are plenty of hosting
companies which offer PC or UltraSparc hosting on Solaris, BSD,
or Linux, one should be able to find a host which will have a setup
comparable to one you can build at home. If you simply can't have
a PC-based box with NetBSD, OpenBSD, FreeBSD, or some form of Linux
at home, then you may want to think about the state of your career
as an IT professional.
Then, of course, there's Windows... If you really want to host on
this bastard child of VMS and DOS, you should be able to get your
hands on NT4 Server/2000 AS, VC++, ActiveState Perl, and a machine
on which to run it all for under $3000 US if you look around
carefully enough. My company offers both 2000 AS hosting and
RH Linux hosting, and many other companies offer both Windows and
Linux hosting.
If one can't have SSH access, can't run make from CGI, and can't
get one's hands on the same setup as the hosting company, perhaps
it's time to look for a different hosting company, or to colocate
your own box in a customer-managed colocation arrangement.
Chris
--
Programming is a tool. A tool is neither good nor evil. It is
the user who determines how it is used and to what ends.
------------------------------
Date: 23 May 2001 17:53:19 +0100
From: nobull@mail.com
Subject: Re: help getting data into hash from MySql
Message-Id: <u9itis6m80.fsf@wcl-l.bham.ac.uk>
"Mike Solomon" <msolomon@3s-technology.com> writes:
> I am querying a MySql database using DBI
>
> I want to get the data into a hash where the key is the column name
This is what fetchrow_hashref() does.
> the closest I have managed so far is :
>
> my $sql = "select * from pers_add";
> my $sth = $dbh->prepare("$sql");
> $sth(execute);
> while (my $ref = $sth->fetchrow_hashref()) {
> $date{'address1'} = $ref->{'address1'};
> $data{'address2'} = $ref->{'address2'};
>
> etc. ....
> }
The stucture you want is already there, it's %$ref. Why do you want
to copy this to %data? Why not work directly with %$ref?
> As I have over 20 fields in my table this method is very laborious
>
> Is there a better way of doing it.
If you are determined to make a copy then the way to copy the
contents of one hash into another is simply an assignment:
%data = %$ref;
--
\\ ( )
. _\\__[oo
.__/ \\ /\@
. l___\\
# ll l\\
###LL LL\\
------------------------------
Date: Wed, 23 May 2001 13:17:37 -0400
From: Andras Malatinszky <andras@mortgagestats.com>
Subject: Re: Help needed - perl to download from secure website
Message-Id: <3B0BF0B1.1D8F4A03@mortgagestats.com>
David Stallcup wrote:
>
> Hello everyone,
>
> I am trying to emulate a http form on a secured website in order to
> download a file directly to our unix box and I'm stuck. Here are the
> grisly details:
Why don't you check out the LWP module. Make sure you read lwcook as
well.
------------------------------
Date: 23 May 2001 18:24:14 +0100
From: nobull@mail.com
Subject: Re: Help needed - perl to download from secure website
Message-Id: <u9d7906ksh.fsf@wcl-l.bham.ac.uk>
David Stallcup <djstall@mail.utexas.edu> writes:
> I am trying to emulate a http form on a secured website in order to
> download a file directly to our unix box and I'm stuck.
Use LWP.
> Here are the grisly details:
Yes, they are grisly aren't they. Is there any reason you are not
using LWP?
> The URL is:
> https://ncsistr.ic.ncs.com/neon/sampdata/$actsslx.htm
That's an HTTPS url. That means that you should connect to
ncsistr.ic.ncs.com on port 433 using SSL and then issue an HTTP
request over the encrypted connection.
> The relevant code that I created is...
...not doing anything of the sort.
But there's nothing wrong with the Perl code (appart from the fact
that it's written for Perl4). I'm not going to go into details about
what you are doing wrong since it's all application-domain stuff
rather than Perl-domain stuff.
If you learnt Perl before there was Perl5 you may want to take some
time-out to learn about Perl5 and what it has to offer. In Perl5, with
suitable modules installed, scripts like yours can be done in a few
lines.
If you learnt Perl after there was Perl5 you may want to take some
time-out to lynch whoever taught you Perl, or if you learnt from a book,
whoever recommended the book.
If you know Perl5 but are using a system with Perl4 installed you may
want to take some time-out to lynch your sysadmin.
--
\\ ( )
. _\\__[oo
.__/ \\ /\@
. l___\\
# ll l\\
###LL LL\\
------------------------------
Date: Wed, 23 May 2001 17:08:44 -0000
From: cberry@cinenet.net (Craig Berry)
Subject: Re: How to tell what version of Perl
Message-Id: <tgnrksa28c9eff@corp.supernews.com>
Sarah (sarah.felske@owens-ill.com) wrote:
: Understand that I have never used Perl, but need to know what version
: we are running on a server. Anyone know how?
If you have access to a shell prompt on the server, execute 'perl -v'.
'perl -V' will give you more detailed configuration info.
If you don't have shell access, you can write a small CGI program to
report back on the version, which is available in the $] variable (see
'perldoc perlvar'). Here's an example.
#!/usr/bin/perl -w
# perlv - CGI program which reports perl version
# Craig Berry (20010523)
use strict;
use CGI qw(:all);
print header,
start_html('Perl version checker'),
h1("Perl version is $]"),
end_html;
--
| Craig Berry - http://www.cinenet.net/~cberry/
--*-- "God becomes as we are that we may be as he is."
| - William Blake
------------------------------
Date: Wed, 23 May 2001 17:36:51 +0100
From: Malte Ubl <ubl@schaffhausen.de>
Subject: HTML::Entities and the Mac :-(
Message-Id: <3B0BE724.3B4540B4@schaffhausen.de>
Hi,
I've been looking for a solutions to this problem for quite while
and there are dozens of posts to this topic on Deja. However, there
seems to be no working solutions.
Web-Browsers on the web behave not very consistently on what encoding
they use for form submissions. IE 5 for Macintosh likes to mix
HTML entities with non encoded characters. Thats why I use this method
for the encoding:
use HTML::Entities;
sub encode_entities_safe {
my $ref;
if (defined wantarray) {
my $x = $_[0];
$ref = \$x; # copy
} else {
$ref = \$_[0]; # modify in-place
}
if($$ref =~ /(&\w+;)/o) { # decode first in case there are already
encoded characters in here
decode_entities($$ref); # encoded characters in here
}
encode_entities($$ref); # do the actual encoding
}
This works well as long as one gets inport in the standard latin encoding,
however as you copy/paste something from a different Macintosh application
you get something like this:
šŠŸ§üŠšŸŠšŸ
for this input:
öäüßüäöüäöü
This doesnt even display correct on a Mac Browser. So my question i whether
you can get do something in advance so the input that you feed to HTML::Entities
gets normalized?
Thank You,
->malte
------------------------------
Date: Wed, 23 May 2001 10:18:18 -0600
From: "Tom Mullenaux" <tom_mullenaux@agilent.com>
Subject: Re: Mathematical Combinations (similar to "Permuting days of the week" thread)
Message-Id: <990634699.449330@goodnews.cos.agilent.com>
Oooh, close. The output from this is:
summer -a -a -a
summer -a -a -b
summer -a -a -c
summer -a -b -a
summer -a -b -b
summer -a -b -c
I really don't need the same option repeated. What I was thinking of would
be more like:
summer -a
summer -b
summer -c
summer -a -b
summer -b -a
...
summer -a -b -c
...
Also, I need to account for options like:
summer -a joe@company.com -b 3 -c
(I would try to stick with one parameter per option instead of having
multiple test parameters per option. For example, I'd just use
joe@company.com with option a, I don't need to test sue@home.com under the
'a' option, also.)
Thanks,
-Tom
"novastar" <root@novastar.dtdns.net> wrote in message
news:990629826.394739@athnrd02.forthnet.gr...
> You mean something like that ?
>
> @options=qw/a b c/;
>
> for $i (0..$#options)
> {
> for $j (0..$#options)
> {
> for $k (0..$#options)
> {
> print "summer -$options[$i] -$options[$j] -$options[$k]\n"
> }
> }
> }
>
>
>
>
> "Tom Mullenaux" <tom_mullenaux@agilent.com> wrote in message
> news:990628478.613542@goodnews.cos.agilent.com...
> > I'm testing some software and would like to programmatically generate a
> list
> > of all possible combinations of command-line options. Any ideas?
> >
> > Thanks
> >
> > -Tom
> >
> >
>
>
------------------------------
Date: Wed, 23 May 2001 18:17:39 +0200
From: "Trond Michelsen" <trondmm-usenet@crusaders.no>
Subject: Re: Mathematical Combinations (similar to "Permuting days of the week" thread)
Message-Id: <rpRO6.68$lM3.893@news1.oke.nextra.no>
"novastar" <root@novastar.dtdns.net> wrote in message
news:990629826.394739@athnrd02.forthnet.gr...
>> I'm testing some software and would like to programmatically generate
a
>> list
>> of all possible combinations of command-line options. Any ideas?
> You mean something like that ?
> @options=qw/a b c/;
>
> for $i (0..$#options)
> {
> for $j (0..$#options)
> {
> for $k (0..$#options)
> {
> print "summer -$options[$i] -$options[$j] -$options[$k]\n"
> }
> }
> }
That's no good.
the wanted result is:
-a
-b
-c
-a -b
-a -c
-b -c
-a -b -c
but your program generates:
-a -a -a
-a -a -b
-a -a -c
-a -b -a
-a -b -b
etc.
--
Trond Michelsen
------------------------------
Date: Wed, 23 May 2001 17:49:31 -0000
From: cberry@cinenet.net (Craig Berry)
Subject: Re: Mathematical Combinations (similar to "Permuting days of the week" thread)
Message-Id: <tgnu1bkppnvac2@corp.supernews.com>
Tom Mullenaux (tom_mullenaux@agilent.com) wrote:
: I'm testing some software and would like to programmatically generate a list
: of all possible combinations of command-line options. Any ideas?
#!/usr/bin/perl -w
# combos - enumberate all combos of arguments (empty list skipped)
# Craig Berry (20010523)
use strict;
my @elems = @ARGV;
die 'No elements on command line' unless @elems;
foreach my $bits (1..2**@elems-1) {
foreach my $e (0..$#elems) {
print "$elems[$e] " if $bits & (1 << $e);
}
print "\n";
}
--
| Craig Berry - http://www.cinenet.net/~cberry/
--*-- "God becomes as we are that we may be as he is."
| - William Blake
------------------------------
Date: Wed, 23 May 2001 17:58:08 GMT
From: tiltonj@erols.com (Jay Tilton)
Subject: Re: Mathematical Combinations (similar to "Permuting days of the week" thread)
Message-Id: <3b0bf4ce.176041365@news.erols.com>
[In future, please post your response below quoted material.]
On Wed, 23 May 2001 10:18:18 -0600, "Tom Mullenaux"
<tom_mullenaux@agilent.com> wrote:
>I really don't need the same option repeated. What I was thinking of would
>be more like:
>
>summer -a
>summer -b
>summer -c
>summer -a -b
>summer -b -a
>...
>summer -a -b -c
>...
>
>Also, I need to account for options like:
>
>summer -a joe@company.com -b 3 -c
See if this can suit your task.
It will work with an arbitrary number of elements in @opts.
my @opts = ('-a joe@company.com', '-b 3', '-c');
for my $i ( 1 .. (1<<$#opts+1)-1 ) {
print 'summer';
for (0..$#opts) {
print " $opts[$_]" if ($i & 1<<$_);
}
print "\n";
}
------------------------------
Date: 23 May 2001 15:06:28 GMT
From: anno4000@lublin.zrz.tu-berlin.de (Anno Siegel)
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <9egjlk$ms0$2@mamenchi.zrz.TU-Berlin.DE>
According to Dave Bailey <dave@sydney.daveb.net>:
> On Wed, 23 May 2001 13:43:18 GMT, Mark Jason Dominus <mjd@plover.com> wrote:
> >In article <slrn9gmm2o.l37.dave@sydney.daveb.net>,
> >Dave Bailey <dave@sydney.daveb.net> wrote:
> [...]
> >>I thought an NP complete problem was one which could be solved in
> >>polynomial time only if you have a way to test an arbitrary number of
> >>candidate solutions simultaneously (i.e. a quantum computer). What
> >>does that have to do with the size of the problem statement?
> >
> >I'm really sorry about this, and I don't want to be rude, [...]
>
> If you're sorry and you don't want to be rude, either answer my
> question or say nothing.
They're so cute when they demand that, aren't they?
> Something along the lines of "the size
> of the problem statement is the quantity in which the solution
> verifier's execution time is a polynomial" would have sufficed.
Indeed, but not everyone has your talent in combining conciseness
with clarity.
Anno
------------------------------
Date: Wed, 23 May 2001 15:21:47 -0000
From: gbacon@HiWAAY.net (Greg Bacon)
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <tgnlcbd0248qdc@corp.supernews.com>
In article <slrn9gmm2o.l37.dave@sydney.daveb.net>,
Dave Bailey <dave@sydney.daveb.net> wrote:
: On Wed, 23 May 2001 03:16:19 GMT, Mark Jason Dominus <mjd@plover.com> wrote:
: >Second, subset-sum is a number problem, and efficient algorithms *do*
: >exist. These algorithms are polynomial in the magnitude of the number
: >N; the reason subset-sum is NP-complete is not that the solution takes
: >a long time, but that it takes a long time *relative to the size of
: >the problem statement*, which is very brief.
:
: I have never heard of this definition of NP-completeness (defining
: it in terms of the problem statement). I thought an NP complete
: problem was one which could be solved in polynomial time only if you
: have a way to test an arbitrary number of candidate solutions
: simultaneously (i.e. a quantum computer). What does that have to
: do with the size of the problem statement?
You're describing something like NP, i.e., the class of decision
problems that can be solved in polynomial (in the size of the problem)
time on a non-deterministic Turing machine. Informally, the problems in
NP-complete are the hardest problems in NP.
ObPerl: Perl regular expression matching is in NP-complete. See
<URL:http://perl.plover.com/NPC/>.
Greg
--
When a true genius appears in this world, you may know him by this sign,
that the dunces are all in confederacy against him.
-- Jonathan Swift
------------------------------
Date: 23 May 2001 11:44:27 -0400
From: Joe Schaefer <joe+usenet@sunstarsys.com>
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <m34ruct6hw.fsf@mumonkan.sunstarsys.com>
mjd@plover.com (Mark Jason Dominus) writes:
> In article <9efgrr$rnj$1@agate.berkeley.edu>,
> Ilya Zakharevich <ilya@math.ohio-state.edu> wrote:
> >There is an alternative, recursion formula, but IIRC it involves a
> >very "wide" recursion.
>
> The recursion is very complicated for a mathematician because of
> multiply-nested summations. But any idiot can compute a few special
> cases, and that is all we need here. It takes O(N^3) time to compute
> all the values needed to solve the problem for N partitioned into P
> parts. Probably there is some obvious identity that I am missing that
> would reduce the time to O(n^2), but it is 3AM here so I will leave it
> alone.
ICBW, but I'm pretty sure the recursion formula Ilya is referring to
is for the partition function p(N) itself, and is due to Euler. Your
straightforward recursion formula for
D(N,K,P) = the number of partitions of N into *exactly* P parts,
each part of size at least K
does not lead to Euler's formula for p, although obviously
p(N) = D(N,1,1) + D(N,1,2) + ... + D(N,1,N-1) + D(N,1,N) .
FWIW, here is Euler's recursion for p (untested):
sub p ($) {
my $n = shift;
return $n >= 0 if $n <= 1;
return $p[$n] if defined $p[$n];
my ($m, $sum);
# loop condition: [x]( 3[x] - 1 ) <= 2 * $n
for (1 .. (( sqrt(1+24*$n)+1 ) / 6) ) {
$m = p($n - int($_*(3*$_ - 1)/2) ) +
p($n - int($_*(3*$_ + 1)/2) ) ;
if ( $_ % 2 == 1 ) { $sum += $m }
else { $sum -= $m }
}
return $p[$n] = $sum;
}
Otherwise no comments on your "3am code"- AFAICT it seems
to be a fine solution to OP's question.
--
Joe Schaefer "The man who sets out to carry a cat by its tail learns
something that will always be useful and which never will grow
dim or doubtful."
--Mark Twain
------------------------------
Date: Wed, 23 May 2001 18:24:01 +0100
From: =?iso-8859-1?Q?Thorbj=F8rn?= Ravn Andersen <thunderbear@bigfoot.com>
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <3B0BF230.9B2CC80E@bigfoot.com>
Greg Bacon wrote:
> You're describing something like NP, i.e., the class of decision
> problems that can be solved in polynomial (in the size of the problem)
> time on a non-deterministic Turing machine. Informally, the problems in
> NP-complete are the hardest problems in NP.
My teacher used to say something regarding NP around the lines of "a
_solution_ to the problem can be verified in linear time".
I.e. whenever you have something to choose from, you peek at the
solution and pick the right one.
Unfortunately, you need to solve the problem first, before you have a
solution, and computers are not very good at guessing.
--
Thorbjørn Ravn Andersen "...plus...Tubular Bells!"
http://bigfoot.com/~thunderbear
------------------------------
Date: Wed, 23 May 2001 16:32:55 +0000 (UTC)
From: abigail@foad.org (Abigail)
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <slrn9gnphn.ngi.abigail@tsathoggua.rlyeh.net>
Thorbjørn Ravn Andersen (thunderbear@bigfoot.com) wrote on MMDCCCXXII
September MCMXCIII in <URL:news:3B0BF230.9B2CC80E@bigfoot.com>:
@@ Greg Bacon wrote:
@@
@@ > You're describing something like NP, i.e., the class of decision
@@ > problems that can be solved in polynomial (in the size of the problem)
@@ > time on a non-deterministic Turing machine. Informally, the problems in
@@ > NP-complete are the hardest problems in NP.
@@
@@ My teacher used to say something regarding NP around the lines of "a
@@ _solution_ to the problem can be verified in linear time".
It turns out that those definitions are equivalent.
Abigail
--
perl -wlpe '}$_=$.;{' file # Count the number of lines.
------------------------------
Date: Wed, 23 May 2001 19:24:32 +0100
From: =?iso-8859-1?Q?Thorbj=F8rn?= Ravn Andersen <thunderbear@bigfoot.com>
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <3B0C0060.B93E546A@bigfoot.com>
Abigail wrote:
>
> Thorbjørn Ravn Andersen (thunderbear@bigfoot.com) wrote on MMDCCCXXII
> September MCMXCIII in <URL:news:3B0BF230.9B2CC80E@bigfoot.com>:
> @@ Greg Bacon wrote:
> @@
> @@ > You're describing something like NP, i.e., the class of decision
> @@ > problems that can be solved in polynomial (in the size of the problem)
> @@ > time on a non-deterministic Turing machine. Informally, the problems in
> @@ > NP-complete are the hardest problems in NP.
> @@
> @@ My teacher used to say something regarding NP around the lines of "a
> @@ _solution_ to the problem can be verified in linear time".
>
> It turns out that those definitions are equivalent.
I am aware of that.
The two definitions are, however, not equally hard to understand for
most people.
--
Thorbjørn Ravn Andersen "...plus...Tubular Bells!"
http://bigfoot.com/~thunderbear
------------------------------
Date: Wed, 23 May 2001 17:59:47 GMT
From: mjd@plover.com (Mark Jason Dominus)
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <3b0bfa92.56c7$1e0@news.op.net>
In article <9egjlk$ms0$2@mamenchi.zrz.TU-Berlin.DE>,
Anno Siegel <anno4000@lublin.zrz.tu-berlin.de> wrote:
>Indeed, but not everyone has your talent in combining conciseness
>with clarity.
The reason I didn't try was that I felt what he said was wrong in so
many ways I couldn't think of any way to correct all of it without
explaining the whole thing from the ground up; I was afraid that if I
included a partial explanation that it would just confirm his mistaken
notion that he understood what was going on.
--
@P=split//,".URRUU\c8R";@d=split//,"\nrekcah xinU / lreP rehtona tsuJ";sub p{
@p{"r$p","u$p"}=(P,P);pipe"r$p","u$p";++$p;($q*=2)+=$f=!fork;map{$P=$P[$f^ord
($p{$_})&6];$p{$_}=/ ^$P/ix?$P:close$_}keys%p}p;p;p;p;p;map{$p{$_}=~/^[P.]/&&
close$_}%p;wait until$?;map{/^r/&&<$_>}%p;$_=$d[$q];sleep rand(2)if/\S/;print
------------------------------
Date: 6 Apr 2001 21:33:47 GMT (Last modified)
From: Perl-Users-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 6 Apr 01)
Message-Id: <null>
Administrivia:
The Perl-Users Digest is a retransmission of the USENET newsgroup
comp.lang.perl.misc. For subscription or unsubscription requests, send
the single line:
subscribe perl-users
or:
unsubscribe perl-users
to almanac@ruby.oce.orst.edu.
To submit articles to comp.lang.perl.announce, send your article to
clpa@perl.com.
To request back copies (available for a week or so), send your request
to almanac@ruby.oce.orst.edu with the command "send perl-users x.y",
where x is the volume number and y is the issue number.
For other requests pertaining to the digest, send mail to
perl-users-request@ruby.oce.orst.edu. Do not waste your time or mine
sending perl questions to the -request address, I don't have time to
answer them even if I did know the answer.
------------------------------
End of Perl-Users Digest V10 Issue 968
**************************************
