[18795] in Perl-Users-Digest
Perl-Users Digest, Issue: 963 Volume: 10
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Wed May 23 03:05:40 2001
Date: Wed, 23 May 2001 00:05:15 -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: <990601514-v10-i963@ruby.oce.orst.edu>
Content-Type: text
Perl-Users Digest Wed, 23 May 2001 Volume: 10 Number: 963
Today's topics:
Re: Algorithm ? <goldbb2@earthlink.net>
Re: Array slice: how about the remainder? <johnlin@chttl.com.tw>
Re: delete() from array <uri@sysarch.com>
Emailing from a script <denverlynx@hotmail.com>
Re: Emailing from a script (Rafael Garcia-Suarez)
Re: FAQ 5.10: How can I output my numbers with commas <c_clarkson@hotmail.com>
foreach loop and chop problem angry_garden_salad@yahoo.com
Go to file's line number. <Francis.Derive@wanadoo.fr>
Re: Go to file's line number. (Rafael Garcia-Suarez)
Re: Go to file's line number. <krahnj@acm.org>
Re: Go to file's line number. <godzilla@stomp.stomp.tokyo>
Re: How can I convert a date (MM/DD/YYYY) to UTC time? <william.c.nelson@gte.net>
Re: how to get the access_log file name in a program <JIMIT@prodigy.net>
Re: Limit on argument length in pipe <goldbb2@earthlink.net>
mod_perl & fast cgi <tom@hotversion.com>
Re: module for combinatorics? (partitions etc) (Mark Jason Dominus)
Re: module for combinatorics? (partitions etc) <ilya@math.ohio-state.edu>
Re: module for combinatorics? (partitions etc) (Mark Jason Dominus)
Re: Permuting days of the week (Eric Bohlman)
Re: Permuting days of the week (Craig Berry)
Re: re-sizing GIF images on the fly <addi@umich.edu>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Wed, 23 May 2001 02:43:51 -0400
From: Benjamin Goldberg <goldbb2@earthlink.net>
Subject: Re: Algorithm ?
Message-Id: <3B0B5C27.B5FBD4F2@earthlink.net>
John Hall wrote:
>
> I'm not going to assault you with 'did you read this novel, did you
> read that novel..'
>
> Here's a good article describing 'tethering' and keeping track of many
> children..
>
> http://www.stonehenge.com/merlyn/LinuxMag/col15.html
It seems very well thought out, but it could be made quite a bit
simpler.
Have one datagram socket (pipe with messages garunteed to be atomic)
from parent to kids, one datagram socket from kids to parent. This
gaurantees messages are read and written atomically. Keep a pool of
kids running. Each kids reads one task from the from_parent pipe, thaws
it, runs it, freezes the result, and writes it to the to_parent pipe.
The parent has a bunch of tasks. It freezes each one, dumps all of them
into the to_kids pipe, each task being a seperate atomic message. It
then reads the results from the from_kids pipe as they come, writing new
tasks into the to_kids pipe as neccessary. We don't even have to keep
track of which kid did which task!
--
Customer: "I would like to try on that suit in the window."
Salesman: "Sorry sir, you will have to use the dressing room."
------------------------------
Date: Wed, 23 May 2001 10:23:01 +0800
From: "John Lin" <johnlin@chttl.com.tw>
Subject: Re: Array slice: how about the remainder?
Message-Id: <9ef6ps$ebk@netnews.hinet.net>
"Chris Stith" wrote
> my @stay_home = ();
> my %chosen = ();
> keys(%chosen) = @chosen;
> for( @array ) {
> unless( exists( $chosen{$_} ) ) {
> push @stay_home, $_;
> }
> }
> I'd imagine it would be more efficient to write the thing as a hash
> initially. ;-)
Since all indexes are integers, I think using an array is more efficient
than hash. (No need to stringify. Takes up less space.)
my @array = 0..70;
my @chosen = (0,3,5,7,21,35,63,66,68);
my @seen; @seen[@chosen] = ();
my @stay_home = @array[grep {!exists $seen[$_]} 0..$#array];
Actually, Anno has proposed a "vec" version in other branch
of this thread which just uses a scalar.
Best regards.
John Lin
--
SUMMARY:
(1) Use copy + delete + grep{exists}
(2) Use splice on reverse sort @chosen
(3) Use %seen, @seen or $seen (with "vec")
------------------------------
Date: Wed, 23 May 2001 01:42:49 GMT
From: Uri Guttman <uri@sysarch.com>
Subject: Re: delete() from array
Message-Id: <x7g0dw6dt2.fsf@home.sysarch.com>
>>>>> "BL" == Bart Lateur <bart.lateur@skynet.be> writes:
BL> Uri Guttman wrote:
BL> But you can't really use it.
>>
BL> @remain = grep { exists $_ } @ary;
>>
BL> doesn't even compile.
>>
>> well, exists needs to be given a real location and not a value.
BL> Well... in the grep block, $_ is an *alias* to the array element, not
BL> just its value.
but we are talking about the array slot and not the value in the slot.
you can have a slot with nothing in it, so you can't take a ref to it or
alias it. or you can have a slot with the undef value in it.
BL> Perhaps I've had a bit too much of the recent discussions on the
BL> Perl6 mailing lists, so I kind of expected exists() to test a
BL> "property" of the array element. That property would also be
BL> accessible through the alias, I guess.
think of the slot as having a variable property like
Contains_something. exists in 5.6 can test that. it is the same using
exists vs defined on a hash key. defined can't tell the difference
between a missing key or a key with the value undef.
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 04:30:05 -0000
From: S E <denverlynx@hotmail.com>
Subject: Emailing from a script
Message-Id: <tgmf6d96itc49f@corp.supernews.com>
Hi,
I am using the below script to send a email with a attachment. But, when
the email to: multiple users I would like the userids to appear on the
same line as you see in most emails. But, this is the only way I know how
to get them on the email currently. Is there a more efficient way to do
this?
#!/usr/local/bin/perl5.6
use lib "lib";
use MIME::Lite;
MIME::Lite->send('smtp', "gp-dragon", Timeout=>180);
$msg = new MIME::Lite
From => 'somebody@gwl.com',
To => 'glcomm@gwl.com',
To => 'prodsupp@gwl.com',
Subject => 'PNP Daily Results',
Type => 'TEXT',
Path
=> "/home/pnp/gp22/SCRIPTS_regular/gainloss/reports/GP22_all_pwgl_rept.txt
",
Encoding => '7bit';
attach $msg
Type => 'TEXT',
Path
=>"/home/pnp/gp22/SCRIPTS_regular/gainloss/reports/GP22_pwgl_user_rept.txt"
,
Filename =>"GP22_pwgl_user_rept.txt";
$msg->send;
--
Posted via CNET Help.com
http://www.help.com/
------------------------------
Date: 23 May 2001 06:38:04 GMT
From: rgarciasuarez@free.fr (Rafael Garcia-Suarez)
Subject: Re: Emailing from a script
Message-Id: <slrn9gmmla.5o1.rgarciasuarez@rafael.kazibao.net>
S E wrote in comp.lang.perl.misc:
} Hi,
}
} I am using the below script to send a email with a attachment. But, when
} the email to: multiple users I would like the userids to appear on the
} same line as you see in most emails. But, this is the only way I know how
} to get them on the email currently. Is there a more efficient way to do
} this?
}
} #!/usr/local/bin/perl5.6
} use lib "lib";
} use MIME::Lite;
} MIME::Lite->send('smtp', "gp-dragon", Timeout=>180);
}
} $msg = new MIME::Lite
} From => 'somebody@gwl.com',
} To => 'glcomm@gwl.com',
} To => 'prodsupp@gwl.com',
Try a single 'To' field :
To => (join ', ', 'glcomm@gwl.com', 'prodsupp@gwl.com'),
--
Rafael Garcia-Suarez / http://rgarciasuarez.free.fr/
------------------------------
Date: Tue, 22 May 2001 22:50:39 -0500
From: "Charles K. Clarkson" <c_clarkson@hotmail.com>
Subject: Re: FAQ 5.10: How can I output my numbers with commas added?
Message-Id: <A154D3DD8D296F7B.B260B079F0C5568F.4211964EC70F0BBC@lp.airnews.net>
I was looking for this faq recently and wondered: why
is it part of perlfaq5 instead of perlfaq4? I realize
formatting is discussed in 5, but it seems more likely to
belong in 4.
Charles K Clarkson
------------------------------
Date: Wed, 23 May 2001 06:48:04 GMT
From: angry_garden_salad@yahoo.com
Subject: foreach loop and chop problem
Message-Id: <E2JO6.4516$r4.271027@www.newsranger.com>
HI,
I have the following script:
#!/usr/bin/perl
@hosts=`cat /u/hosts`;
@lists=`cat /u/lists`;
foreach $host ( @hosts ) {
chop $host;
foreach $list ( @lists ) {
chop $list;
if ( $host eq $list ) {
print "they match!!\n";
}
}
}
I'm running this on linix and my input files, hosts and lists, have carriage
returns in then. This is why I need to chop them. My problem is that my $list
variable chops the carriage return on the first pass, but on the second, third,
etc... pass, it keeps chopping the variable until there's nothing left. Why? I
thought each time I read the @lists array, the carriage return would still be in
there, but it's not. I have to re-read the @lists array before I go into the
foreach for this to work but I don't want to read from disk everytime, my lists
are kinda big. This is what I had to do to get it to work:
#!/usr/bin/perl
@hosts=`cat /u/hosts`;
foreach $host ( @hosts ) {
chop $host;
@lists=`cat /u/lists`;
foreach $list ( @lists ) {
chop $list;
if ( $host eq $list ) {
print "they match!!\n";
}
}
}
Shouldn't my first example work? How can I fix this so that I only have to read
the file once and remove all the carriage returns? Any input would be great,
thanks.
------------------------------
Date: 23 May 2001 08:10:42 +0200
From: "Francis Derive" <Francis.Derive@wanadoo.fr>
Subject: Go to file's line number.
Message-Id: <B7312109-12519@193.248.254.18>
Bonjour !
I want to access several lines, here and there, in a file.
I was surprised to only conceive a basic treatment :
for $line_number ( 1 .. $my_line_number ) {
if (defined($line = <FILE>)) {
<FILE>; # pass by
}
}
$line = <FILE>; # I get it.
It is only but sequential, isn't ?
--
I know I could read the whole file in a hash in memory, with each line
number associated with the very line, and then access the content of each
line I wish, directly.
---
But this means to read the whole file in memory, which can be big. I met a
80 000 lines file I could not read in a hash - memory problem -.
----
I imagine Perl has a sophisticated way to proceed with this question.
Thanks to help.
Francis.
------------------------------
Date: 23 May 2001 06:29:24 GMT
From: rgarciasuarez@free.fr (Rafael Garcia-Suarez)
Subject: Re: Go to file's line number.
Message-Id: <slrn9gmm52.5o1.rgarciasuarez@rafael.kazibao.net>
Francis Derive wrote in comp.lang.perl.misc:
}
} Bonjour !
}
} I want to access several lines, here and there, in a file.
} I was surprised to only conceive a basic treatment :
}
} for $line_number ( 1 .. $my_line_number ) {
} if (defined($line = <FILE>)) {
} <FILE>; # pass by
This doesn't work. You're reading each line twice here.
} }
} }
} $line = <FILE>; # I get it.
In fact you're getting the line 1+2*$my_line_number.
} It is only but sequential, isn't ?
}
} --
}
} I know I could read the whole file in a hash in memory, with each line
} number associated with the very line, and then access the content of each
} line I wish, directly.
If you want to use a number as a key, an array is better.
} ---
}
} But this means to read the whole file in memory, which can be big. I met a
} 80 000 lines file I could not read in a hash - memory problem -.
}
} ----
}
} I imagine Perl has a sophisticated way to proceed with this question.
There are several possible solutions.
One of them is probably to use a database in place of a plain text file.
Another solution is to use a file with fixed-length lines, so you can
use the seek() function to move easily into the file.
--
Rafael Garcia-Suarez / http://rgarciasuarez.free.fr/
------------------------------
Date: Wed, 23 May 2001 06:32:37 GMT
From: "John W. Krahn" <krahnj@acm.org>
Subject: Re: Go to file's line number.
Message-Id: <3B0B5980.FF689868@acm.org>
Francis Derive wrote:
>
> Bonjour !
>
> I want to access several lines, here and there, in a file.
> I was surprised to only conceive a basic treatment :
>
> for $line_number ( 1 .. $my_line_number ) {
> if (defined($line = <FILE>)) {
> <FILE>; # pass by
> }
> }
> $line = <FILE>; # I get it.
>
> It is only but sequential, isn't ?
>
> I know I could read the whole file in a hash in memory, with each line
> number associated with the very line, and then access the content of each
> line I wish, directly.
>
> But this means to read the whole file in memory, which can be big. I met a
> 80 000 lines file I could not read in a hash - memory problem -.
>
> I imagine Perl has a sophisticated way to proceed with this question.
No need to read the whole file into memory.
while ( <FILE> ) {
if ( $. == $my_line_number ) {
# do something with this line
}
}
John
--
use Perl;
program
fulfillment
------------------------------
Date: Tue, 22 May 2001 23:42:47 -0700
From: "Godzilla!" <godzilla@stomp.stomp.tokyo>
Subject: Re: Go to file's line number.
Message-Id: <3B0B5BE7.5847888A@stomp.stomp.tokyo>
Francis Derive wrote:
> Bonjour !
Bon Bons are better.
(snippage)
> I want to access several lines, here and there, in a file.
> I know I could read the whole file in a hash in memory, with each line
> number associated with the very line....
Research and read about $. usage.
while (<TROLL_ARTICLE>)
{
if ($. == selected line number)
{ &Reformat_Your_Hard_Drive; }
}
You would be _very_ wise to do your homework on this.
Godzilla!
------------------------------
Date: Wed, 23 May 2001 02:14:39 GMT
From: Bill Nelson <william.c.nelson@gte.net>
Subject: Re: How can I convert a date (MM/DD/YYYY) to UTC time?
Message-Id: <3B0B17A5.E6014CCA@gte.net>
This is a multi-part message in MIME format.
--------------6572A2FF348283A6F1BDDCEA
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
You are correct, I actually misstated the question. Let me try again.
I have an application that provides logfiles with entries containing
timestamps in the number of seconds since the Epoch (00:00:00 UTC, January 1,
1970). In trying to create a human readable log file, I can convert each
timestamp to a human readable time/date format by using the gmtime()
function. For instance,
$secondsSinceEpoch = 954991003;
$humanReadableTimeStamp = gmtime($secondsSinceEpoch);
That produces a value of "Tue Mar 27 14:01:42 2001" for the
$humanReadableTimestamp scalar variable.
Now, I want to be able to allow users to enter in a starting date and ending
date so I can only show entries in this log that fall between the starting
date and ending date. I can control the way that they enter in the date
format so that I can extract the month, day, and year from both dates.
I am assuming that the easiest way would be to simply take the dates that they
enter and convert them into the number of seconds since the Epoch. I could
then compare easily by doing something like:
if ( ($secondsSinceEpoch >= $startingDate) && ($secondsSinceEpoch <=
$endingDate) ) {
# print the log entry
}
I simply need to see if there is a way to take a date (ie 12/31/2001) and
convert it into the number of seconds since the Epoch.
Hopefully this is less confusing.
THANKS AGAIN!
bill
"Jürgen Exner" wrote:
> "Bill Nelson" <william.c.nelson@gte.net> wrote in message
> news:3B0AD4D0.6727AC4E@gte.net...
> > I would like to do some date comparrisons via UTC time and am trying to
> > determine how to converte a date format of something like: 12/01/2000
> > to UTC without having to do all the math and figure out leap years and
> > such.
>
> I think you are somewhat confused. Your question doesn't make much sense.
> - A date is something like e.g. 2001/05/22 (in whatever standard).
> - A time is something like e.g. 18:34 o'clock, (and you are asking for the
> timezone being in UTC).
> They have pretty much nothing to do with each other and you simply cannot
> convert a data into a time (be it UTC or any other time zone).
>
> Maybe your date contains a time segment and you are trying to convert this
> segment to UTC? Then you may want to look up locales and timezones.
> Or are you asking for something totally different?
>
> jue
--------------6572A2FF348283A6F1BDDCEA
Content-Type: text/x-vcard; charset=us-ascii;
name="william.c.nelson.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Bill Nelson
Content-Disposition: attachment;
filename="william.c.nelson.vcf"
begin:vcard
n:Nelson;Bill
tel;pager:727.468.6779
tel;cell:727.365.5677
tel;fax:727.579.1107
tel;work:727.576.0549 x213
x-mozilla-html:FALSE
url:http://www.bnelson.com
adr:;;;;;;
version:2.1
email;internet:isstb@flanet.com
title:Consultant/Trainer/Developer
fn:Nelson, Bill
end:vcard
--------------6572A2FF348283A6F1BDDCEA--
------------------------------
Date: Tue, 22 May 2001 22:38:18 -0500
From: "Jimi Thompson" <JIMIT@prodigy.net>
Subject: Re: how to get the access_log file name in a program
Message-Id: <9efb0q$5ep8$1@newssvr05-en0.news.prodigy.com>
Assign it a variable and either have the user fill it in or have the program
scan the folder where the log files are kept. FYI, that may be changing
with Apache 2.0.
Tulan W. Hu <twhu@lucent.com> wrote in message
news:9ebot3$3i7@nntpb.cb.lucent.com...
> I can get the server name from the Apache module via the
> $r->server->server_hostname.
> Is there a way to get the file name of TransferLog or CustomLog from the
> Apache module?
>
>
>
------------------------------
Date: Wed, 23 May 2001 01:46:35 -0400
From: Benjamin Goldberg <goldbb2@earthlink.net>
Subject: Re: Limit on argument length in pipe
Message-Id: <3B0B4EBB.C08CE246@earthlink.net>
Patrick L. Nolan wrote:
>
> I have a script which includes a line like this:
> open (MAIL, "| /usr/lib/sendmail $addresslist") or die;
>
> $addresslist is a string which contains a series of e-mail addresses
> separated by commas. It works OK for my test cases, but I worry
> that real life operation may produce a list that's too big to
> handle.
I don't know, but you shouldn't be feeding in the addresses on the
commandline anyway. Use the -t option, and give the addresses on the
first line of input.
open my $sendmail, "| /usr/lib/sendmail -t" or die;
print $sendmail, "To: $addresslist\n"
> Does anyone know what sort of limits apply to this situation?
> If it makes a difference, it's perl version 5.005_03 on Red Hat
> Linux 6.2.
A limit on the length of the argument list might be defined by the
operating system, but perl does not define any such limit, AFAIK.
Anyway, as I said you should not be using the commandline to pass
addresses to sendmail. What would happen if I claimed that my email
address was "god@heaven|rm -rf /;.org" ? After interpolation, there
will be two | characters in the command, so that perl will use the
shell, and as a result run the command "rm -rf /". This would be Bad.
--
Customer: "I would like to try on that suit in the window."
Salesman: "Sorry sir, you will have to use the dressing room."
------------------------------
Date: Wed, 23 May 2001 05:59:37 GMT
From: "Tom" <tom@hotversion.com>
Subject: mod_perl & fast cgi
Message-Id: <dlIO6.26136$BU4.43535@news1.blktn1.nsw.optushome.com.au>
Hi guys
I'm a little confused about mod_perl and fast cgi which one is faster ?
Tom
------------------------------
Date: Wed, 23 May 2001 03:16:19 GMT
From: mjd@plover.com (Mark Jason Dominus)
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <3b0b2b74.42e6$235@news.op.net>
In article <slrn9gllaa.k9e.dave@sydney.daveb.net>,
Dave Bailey <dave@sydney.daveb.net> wrote:
>Producing a random permutation is easy because all that is needed to
>ensure randomness is the list of indices picked at each step.
Well, I realize that I'm getting into the reason why your argument
that my argument that Cardwell's argument doesn't apply doesn't apply
doesn't apply. But I think your argument doesn't apply.
Given a number i between 1 and n!, I can find the nth permutation on
the list of all permutations, even without enumerating all the
permutations. There is an exponential number of permutations, but
nevertheless I can produce any permutation #n without any trouble.
Given this, it's easy to produce a random permutation: Select an
integer from 1 to n! at random, and then produce the corresponding
permutation.
I believe a similar thing should be possible for partitions, in
subexponential time. That is, it's not hard to figure out how many
partitions there are of the original number X; then generate a random
number i between 1 and P(X); then generate partition number i.
To be more specific, I think you can do tree search on the partitions.
For example, suppose you are trying to partition the number 11 in 4
parts. Then you construct the following notional tree:
+-+--+----- 1118
| | +----- 1127
| | +----- 1136
| | +----- 1145
| |
| +--+----- 1226
| | +----- 1235
| | +----- 1244
| |
| +-------- 1334
|
+-+--+----- 2225
| +----- 2234
|
+-------- 2333
(You don't have to actually construct the tree itself; you only need
to have it in mind.) Now, if I can (in polynomial time) number each
internal node with the total number of leaves below that node, then I
win:
11-8--4----- 1118
| | +----- 1127
| | +----- 1136
| | +----- 1145
| |
| +--3----- 1226
| | +----- 1235
| | +----- 1244
| |
| +--1----- 1334
|
+-3--2----- 2225
| +----- 2234
|
+--1----- 2333
I win because I can trace a random path from the root, choosing a
subnode at random at each step, and weighting each choice by the
number of leaves below its subnode. (In this example, the first
decision chooses the top branch, 1XXX, with probability 8/11, and the
bottom branch, 2XXX, with probability 3/11. If the top branch is
chosen, the next decision chooses among the three branches 11XX, 12XX,
and 13XX with probabilities 4/8, 3/8, and 1/8 respectively. If the
top branch is chosen again, the final decision chooses between 1118,
1127, 1136, and 1145 equiprobably.)
There are two ways this might fail to be polynomial time. There might
be a bad case where I would have to generate exponentially many
labels, or it might take me exponential time to generate some of the
labels. I believe the label generation can be done in O(X^2) time
just by running the obvious recursive function for the number of
partitions of X. It seems to me that the number of nodes can't grow
too large because you are chopping out most of the branches of the
tree. But if you have a counterargument along these lines I'd be
interested to hear it.
>The problem posed in this thread is (I think) NP complete
>and is probably reducible to the (NP complete) subset sum problem if
>we accept bounds on the range of integers which may be employed in
>constructing a solution.
The problem does have such bounds. If you're trying to partition the
number X, the integers employed in the solution must be in [1..X].
If you allow integers lress than 1, the problem is no longer
well-posed. Allowing integers larger than X does not change the
problem because such integers are useless.
But I have two problems with your guess about NP-completeness. First,
I don't see how you are going to reduce it to subset-sum. Suppose
you're given an algorithm which, given X, produces a partition of X
into integers. (Such partition is always possible.) How are you
going to use that to construct an alrogithm which solves subset-sum?
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. So even a reduction of
this problem to subset-sum (which I doubt) would not suffice to show
that this problem can't be solved efficiently.
--
@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: 23 May 2001 05:12:27 GMT
From: Ilya Zakharevich <ilya@math.ohio-state.edu>
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <9efgrr$rnj$1@agate.berkeley.edu>
[A complimentary Cc of this posting was sent to
Mark Jason Dominus
<mjd@plover.com>], who wrote in article <3b0b2b74.42e6$235@news.op.net>:
> I believe a similar thing should be possible for partitions, in
> subexponential time. That is, it's not hard to figure out how many
> partitions there are of the original number X;
I hope you remember the incredible sophistry Hardy and Ramanujan put
into their formula for the number of partitions! [See Littlewood's
Mathematical Miscelannia for details.]
There is an alternative, recursion formula, but IIRC it involves a
very "wide" recursion.
There is (quite recent and incomplete) theory how the "typical"
partitions look like. But I do not remember even how the largest
number in a partition is distributed (asymptotically).
Note that if you know the exact distribution of the largest numbers in
partitions of n, you can apply a recursive algorithm to get "the k-th
partition" step by step, starting from the largest number down
(similar to what is done for permutations). It may happen that the
fantastic coincidences leading to Hardy-Ramanujan formula are
applicable also to the number of partitions of n with parts bounded by
m. Then you get a polynomial time algo for the problem.
I did not unpack my books yet, so cannot check the details of this.
BTW, I hope people realize that assiging the same weight to each
partition is not the only and not even the most interesting
distribution. "More useful" distributions are related to the "hook
formula": Draw a partition 4+4+3+1+1+1 as
x x
x x x
x x x
x x x x x x
(each column represents a summand). Now replace each x by the "length
of the hook at this position". E.g., the hook of X below consists of
X and o's:
x o
x o x
x X o
x x x x x x
so X should be replaced by 4. This leads to
2 1
4 3 1
5 4 1
9 8 6 3 2 1
and the product of them is 1244160 (via perl -nle "BEGIN{$x=1}
END{print $x} $x *= $_ for split"). One "interesting" distribution
takes this partition with the relative weight 1244160**2, another one
with the weight 1244160. [Do not ask me why! ;-]
Ilya
------------------------------
Date: Wed, 23 May 2001 07:00:29 GMT
From: mjd@plover.com (Mark Jason Dominus)
Subject: Re: module for combinatorics? (partitions etc)
Message-Id: <3b0b600a.47eb$355@news.op.net>
In article <9efgrr$rnj$1@agate.berkeley.edu>,
Ilya Zakharevich <ilya@math.ohio-state.edu> wrote:
>[A complimentary Cc of this posting was sent to
>Mark Jason Dominus
><mjd@plover.com>], who wrote in article <3b0b2b74.42e6$235@news.op.net>:
>> I believe a similar thing should be possible for partitions, in
>> subexponential time. That is, it's not hard to figure out how many
>> partitions there are of the original number X;
>
>I hope you remember the incredible sophistry Hardy and Ramanujan put
>into their formula for the number of partitions! [See Littlewood's
>Mathematical Miscelannia for details.]
I don't know just what you're getting at here, but if Hardy and
Ramanujan had trouble, it was probably because they were solving a
much harder problem than ours. They wanted the partition counting
function in closed form. For this application our task is much
easier. We don't care about understanding the partition counting
function; we just want to compute it.
>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.
Here for inspection is a sample implementation:
----------------------------------------------------------------
use POSIX 'ceil';
# number of partitions into at least p parts of size at least k each
sub D {
my ($n, $k, $p) = @_;
return $n == 0 if $p == 0;
return 0 if $n < $k * $p;
return 1 if $n == $k * $p;
return $D{$n,$k,$p} if exists $D{$n,$k,$p};
my $sum = 0;
for my $i ($k..$n) {
$sum += D($n-$i, $i, $p-1);
}
$D{$n,$k,$p} = $sum;
return $sum;
}
# generate (equiprobably) a partition of $n into exactly $p parts
sub random_partition {
my ($n, $p) = @_;
my $k = 1; # minimum part size
my @partition = (); # the result
for my $d (1..$p) {
my $total_leaves = 0;
my $next_part;
for my $i ($k..ceil($n/($p-$d+1))) {
# $i is our 'guess' for the size of the next part
my $leaves = D($n-$i, $i, $p-$d);
$total_leaves += $leaves;
next unless $total_leaves;
$next_part = $i if rand() < $leaves/$total_leaves;
}
push @partition, $next_part;
$n -= $next_part;
$k = $next_part;
}
return @partition;
}
my ($N, $P) = @ARGV;
$N ||= 11;
$P ||= 4;
for (1..11000) {
++$h{join(",", random_partition($N, $P))};
print STDERR "$_\n" if $_ % 1000 == 0;
}
for my $k (sort {$h{$a}<=>$h{$b}} keys %h) {
print "$k\t$h{$k}\n";
}
----------------------------------------------------------------
--
@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: 23 May 2001 02:01:15 GMT
From: ebohlman@omsdev.com (Eric Bohlman)
Subject: Re: Permuting days of the week
Message-Id: <9ef5lb$1c1$6@bob.news.rcn.net>
James Weisberg <chadbour@wwa.com> wrote:
> Given the days of the week: Sun, Mon, Tue, Wed, Thu, Fri, Sat
> I would like to take various permuations and sequences of those strings
> and fill the days in between. Examples:
Think "arithmetic modulo 7."
------------------------------
Date: Wed, 23 May 2001 03:35:57 -0000
From: cberry@cinenet.net (Craig Berry)
Subject: Re: Permuting days of the week
Message-Id: <tgmc0tegnimi96@corp.supernews.com>
James Weisberg (chadbour@wwa.com) wrote:
: Given the days of the week: Sun, Mon, Tue, Wed, Thu, Fri, Sat
: I would like to take various permuations and sequences of those strings
: and fill the days in between. Examples:
:
: Sun-Sat = "Sun,Mon,Tue,Wed,Thu,Fri,Sat"
: Mon-Sun = "Mon,Tue,Wed,Thu,Fri,Sat,Sun"
: Wed-Tue = "Wed,Thu,Fri,Sat,Sun,Mon,Tue"
: etc, and sub-sequences:
: Sun-Tue = "Sun,Mon,Tue"
: Fri-Sun = "Fri,Sat,Sun"
#!/usr/bin/perl -w
# Generate span of days between argument 3-letter day names
# Craig Berry (20010522)
use strict;
my @days = qw(Sun Mon Tue Wed Thu Fri Sat);
my %after;
$after{$days[$_]} = $days[$_+1] foreach (0..$#days-1);
$after{Sat} = 'Sun';
my ($from, $to) = @ARGV;
my @span;
my $d;
for ($d = $from; $d ne $to; $d = $after{$d}) {
push @span, $d;
}
push @span, $d;
print join ',', @span;
--
| 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 06:36:44 GMT
From: Arnar M Hrafnkelsson <addi@umich.edu>
Subject: Re: re-sizing GIF images on the fly
Message-Id: <m3k8387ep9.fsf@steypa.ast.is>
Andrew Boswell <graham@dragroup.com> writes:
> I want to write a Perl script that examines a GIF file to determine the
> image size (width and height in pixels), then creates a thumbnail of it
> on the fly. Writing the script poses few problems, but how do you
> determine the size of a GIF image? I have downloaded the CompuServe
> GIF89a Spec but that doesn't seem to help much. I know that binary files
> are not meant to be read by humans, only computers, so how and with what
> do I read a (binary) GIF file on the fly, and extract the information I
> want?
> --
> Graham Stow
> DENIS ROONEY ASSOCIATES
> graham@dragroup.com
> http://www.dragroup.com
Hey Andrew, I thought I'd chip in what I think about this whole thing.
I've skimmed most of the other replies and they have some good points
but I think I can add some.
It's not a good idea to send an image to a browswer use the height and
width tags to change the size of the image. The image is generally
bigger than it has to be and it also means that the conversion is done
in the browser. Most browsers use nearest neighbor sampling, they
just use the value of the nearest pixel. This generally leads to a
problem called aliasing and the result is that images look noisy.
The method used by gimp, photoshop and ImageMagick are generally some
sort of interpolation or, more generally, resampling.
It's important to know what kind of images you are working with. If
your images are similar to text small text then using these resampling
methods may cause them to appear smoothed or blurry.
It's likely that some of ImageMagick, Photoshop or gimp support
scaling using the nearest neighbor method which is generally MUCH
MUCH faster than using the resampling methods.
Another aspect is that you want to save the scaled version again as
gif. The gif format is limited to 256 color palettes. But if you
scale using interpolation the resulting image is likely to contain
much greater number of colors than the original. This causes your
image to re-color quantized. Meaning that the palette is regenerated.
Gif also employes LZW compression which is patented by UNISYS for at
least the next 3 years. This means that you should get a license from
UNISYS before using unlicensed programs for generating LZW compressed
gifs with unlicensed (free) versions of ImageMagick and Gimp.
I would try to use png images instead of gifs for the thumbnails. PNG
is a superior format in every way as long as you don't need
animations, which I think you don't need according to your description.
Lastly scaling images is a very cpu and memory intensive process,
especially as the images become bigger. Doing it on the fly may put a
very high load on your server. It may be a better idea to generate
the thumbnails when you put the larger version on the server.
<shameless plug>
Since I wrote the Imager module I'll include example code of generating a
thumbnail using that.
------- CODE -------
#!/usr/bin/perl -w
use Imager;
$img = Imager->new();
$img->open(file=>"image.gif") or die $img->errstr;
$thumb = $img->scale(xpixels => 100, ypixels => 80, type => 'min');
$thumb->write(file=>"thumb.png") or die $img->errstr;
print "Thumbnail Width: ",$thumb->getwidth() ,"\n";
print "Thumbnail Height: ",$thumb->getheight(),"\n";
-------------------
That example makes sure that the thumbnail fills as much of a 100x80
square while maintaining the original aspect ratio. By default the
scale method uses resampling, if you should want to use a nearest
neighbor sampling you can do so by supplying qtype=>'preview' to the
scale method.
Hope this helps, Arnar.
------------------------------
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 963
**************************************
