Arbitrarily Many Nested Loops
Jacob JKW
-------------
#!perl
for (my $i = 0; $i<=$n_ra->[0]; $i++) {
for (my $j = 0; $j<=$n_ra->[1]; $j++) {
for (my $k = 0; $k<=$n_ra->[2]; $k++) {
$prob_ra->[$i+$j+$k] += (
$f_raa->[0]->[$i] *
$f_raa->[1]->[$j] *
$f_raa->[2]->[$k] *
);
}
}
-------------
But that's obviously messy and more imprtantly I'd like to be able to
decide at run time to have how nested levels to go (probably be on the
order of 50 or 60). I assume that there's a canonical manner in which
this should be handled (using closures I'd guess) but I can't
sufficiently summarize my issue to make it Google-able.
Any advice?
Many Thanks,
J.
A. Sinan Unur
@u72g2000cwu.googlegroups.com:
You need to work a little on explaining the problem and algorithm.
Neither the code snippet above nor your verbal description makes any
sense to me, but I am curious to understand why such a monstrosity is
needed.
Sinan
--
A. Sinan Unur <1u...@llenroc.ude.invalid>
(remove .invalid and reverse each component for email address)
comp.lang.perl.misc guidelines on the WWW:
http://augustmail.com/~tadmc/clpmisc/clpmisc_guidelines.html
Ilya Zakharevich
A. Sinan Unur
<1u...@llenroc.ude.invalid>], who wrote in article <Xns9795CB63AB7D...@127.0.0.1>:
> You need to work a little on explaining the problem and algorithm.
> Neither the code snippet above nor your verbal description makes any
> sense to me
I'm afraid the problem is on your side. The explanation-by-code looks
absolutely clear to me.
Looks like there is a multi-dimensional array of unknown-in-advance
dimension. It is known that it is "rectangular"; the sizes are stored
in another vector (one size per dimension).
One wants a CONVENIENT way to run through the elements of this array.
One hint to OP: since you do not know the dimension at compile
time, you cannot be sure that the index of 1st,2nd,3rd etc
dimensions is $k, $l, $m etc. So the only solution is to have the
running index to be an array too: $I[0], $I[1], $I[3] etc.
This more or less immediately suggests a possible solution...
Hope this helps,
Ilya
P.S. One could also use Math::Pari's forvec(); might be a little bit
heavy-weight solution, but maybe then you will find some use for
other functions in Math::Pari too. ;-)
Jim Gibson
Jacob JKW <jaco...@yahoo.com> wrote:
This question was asked several weeks ago, and Anno Siegel had a most
elegant solution. I googled for it but couldn't find. While I can't
hope to reproduce Anno's elegance, here is one possible solution in
three dimensions which can be extended to more dimensions:
#!/usr/local/bin/perl
use warnings;
use strict;
my @n_ra = ( 3, 4, 2 );
my $len = @n_ra;
my( $prob_ra, $f_raa );
for my $i ( 0 .. $#n_ra ) {
for my $j ( 0 .. $n_ra[$i] ) {
$f_raa->[$i]->[$j] = rand;
}
}
my @current = ( 0 ) x $len;
my $position = $#n_ra;
while( $position >= 0 ) {
process(\@current);
$position = $#n_ra;
while( $position >= 0 ) {
if( $current[$position] < $n_ra[$position] ) {
$current[$position]++;
last;
}else{
$current[$position] = 0;
$position--;
}
}
}
for my $i ( 0 .. $#{$prob_ra} ) {
print "\$prob_ra[$i] = $prob_ra->[$i]\n";
}
sub process
{
my $current = shift;
print "processing (", join(',',@$current), ")\n";
my $index = 0;
my $prob = 1;
for my $i ( 0 .. $#{$current} ) {
$index += $current->[$i];
$prob *= $f_raa->[$i]->[$current->[$i]];
}
$prob_ra->[$index] += $prob;
}
which produces ...
processing (0,0,0)
processing (0,0,1)
processing (0,0,2)
processing (0,1,0)
processing (0,1,1)
processing (0,1,2)
processing (0,2,0)
processing (0,2,1)
processing (0,2,2)
.
. [48 lines snipped]
.
processing (3,4,0)
processing (3,4,1)
processing (3,4,2)
$prob_ra[0] = 0.0410682133293649
$prob_ra[1] = 0.136947054256266
$prob_ra[2] = 0.314276516273359
$prob_ra[3] = 0.518803631872173
$prob_ra[4] = 0.736548073593054
$prob_ra[5] = 0.880817464919632
$prob_ra[6] = 0.737055690539397
$prob_ra[7] = 0.623231710116926
$prob_ra[8] = 0.33823563959137
$prob_ra[9] = 0.0982766937328925
Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com
John W. Krahn
Easy enough to do in perl:
my $index_var = 'aa';
my @var_names = map '$' . $index_var++, 0 .. $#$n_ra;
my $nested_loop = join( '',
map "\t" x $_
. 'for ( my '
. $var_names[ $_ ]
. ' = 0; '
. $var_names[ $_ ]
. ' <= $n_ra->[ '
. $_
. ' ]; '
. $var_names[ $_ ]
. "++ ) {\n", 0 .. $#$n_ra )
. "\t" x $#$n_ra
. '$prob_ra->[ '
. join( ' + ', @var_names )
. " ] +=\n"
. join( " *\n",
map "\t" x @$n_ra
. '$f_raa->[ '
. $_
. ' ]->[ '
. $var_names[ $_ ]
. ' ]', 0 .. $#$n_ra )
. "\n"
. join '', map "\t" x $_ . "}\n", reverse 0 .. $#$n_ra;
eval $nested_loop;
John
--
use Perl;
program
fulfillment
Jacob JKW
> [A complimentary Cc of this posting was sent to
> A. Sinan Unur
> <1u...@llenroc.ude.invalid>], who wrote in article <Xns9795CB63AB7D...@127.0.0.1>:
> > You need to work a little on explaining the problem and algorithm.
> > Neither the code snippet above nor your verbal description makes any
> > sense to me
> I'm afraid the problem is on your side. The explanation-by-code looks
> absolutely clear to me.
*should* have written was:
But that's obviously messy and more imprtantly I'd like to be able to
Possibly that's vaguely more clear.
> Looks like there is a multi-dimensional array of unknown-in-advance
> dimension. It is known that it is "rectangular"; the sizes are stored
> in another vector (one size per dimension).
You got it exactly. :-)
[OT Description - I'm using this to create a binomial-style probability
distribution where the success probability differs between trials. For
example. If I flip n different coins, each one biased to a known
extent, m(i) times each what would the probability be of flipping x
heads?]
> One wants a CONVENIENT way to run through the elements of this array.
The way I'd put it would be that I want a way to run through the
elements of the array without having to resort to copy-and-paste.
> One hint to OP: since you do not know the dimension at compile
> time, you cannot be sure that the index of 1st,2nd,3rd etc
> dimensions is $k, $l, $m etc. So the only solution is to have the
> running index to be an array too: $I[0], $I[1], $I[3] etc.
Most definitely . I had just posted the first kludge I came up with.
> This more or less immediately suggests a possible solution...
I have to admit, I don't really see the possible solution you have in
mind here ...
> P.S. One could also use Math::Pari's forvec(); might be a little bit
> heavy-weight solution, but maybe then you will find some use for
> other functions in Math::Pari too. ;-)
Self-promote much? ;-)
David Formosa (aka ? the Platypus)
I quickly worked out one way to do this, no guarties as to effeceny.
sub closefor (&$@) {
my $sub = shift;
my $range = shift;
return sub {
for my $i (0..$range){
$sub->($i,@_)
}
}
}
sub mulitloop (&@) {
my $sub = shift;
for (@_) {
my $oldsub = $sub;
$sub = closefor {$oldsub->(@_)} $_;
}
$sub->();
}
Your code becomes
mulitloop { my $i = shift;
my $j = shift;
my $k = shift;
$prob_ra->[$i+$j+$k] += $f_raa->[0]->[$i] *
$f_raa->[1]->[$j] *
$f_raa->[2]->[$k]
} @$n_ra;
To convert the algorithm into something that does arbitrarily depth
involves a small reworking the insides so that it works with an
arbitrary number of arguments.
mulitloop {
my $sum = 0;
my $product = 1;
for (my $i; $i<=@#_; $i++) {
$sum += $_[$i];
$product *= $f_raa->[$i]->[$_[$i]];
}
$prob_ra->[$sum] += $product;
} @$n_ra;
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Free the Memes.
Jacob JKW
you very, very much for that. :-)
(Thanks to Jim Gibson and John Krahn who both answered my post as well,
for no particularly good reason I didn't get a chance to try out either
of their code samples.)
> --
> Please excuse my spelling as I suffer from agraphia. See
> http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Do you think if I became agraphic I could become as good a programmer
as you?
Ron Savage
Hi Jacob
Glad to see you obtained a solution.
Just for the record, this was discussed in a book by the Australian programmer
Ian Oliver:
Programming Classics
Ian Oliver
Prentice Hall
1993
0-13-100413-1
Section 4.3 Page 87
Computing sub-subtotals within subtotals within totals to any depth
Jacob JKW
David Formosa (aka ? the Platypus) wrote:
significantly than my original ugly cut-and-paste style, which I
suppose shouldn't have come as any surprise as when is elegance ever
free?
Anyway, I'm going to keep this code for further use and some later
date, but I eventyually went with John Krahn eval method posted above.
Ugly but fast,
Thanks again for your help.
Jacob JKW
always had a problem with the brute force ugliness of eval. But the
truth is that even if not the prettiest, this is simply the fastest and
most direct way to go.
Highly appreciate the advice and the ready to go out the box code. :-)
Jacob JKW
Anno Siegel
> In article <1143679874.6...@u72g2000cwu.googlegroups.com>,
> Jacob JKW <jaco...@yahoo.com> wrote:
>
> > This is what I have:
> >
> > -------------
> > #!perl
> >
> > for (my $i = 0; $i<=$n_ra->[0]; $i++) {
> > for (my $j = 0; $j<=$n_ra->[1]; $j++) {
> > for (my $k = 0; $k<=$n_ra->[2]; $k++) {
> > $prob_ra->[$i+$j+$k] += (
> > $f_raa->[0]->[$i] *
> > $f_raa->[1]->[$j] *
> > $f_raa->[2]->[$k] *
> > );
> > }
> > }
> > -------------
> > But that's obviously messy and more imprtantly I'd like to be able to
> > decide at run time to have how nested levels to go (probably be on the
> > order of 50 or 60). I assume that there's a canonical manner in which
> > this should be handled (using closures I'd guess) but I can't
> > sufficiently summarize my issue to make it Google-able.
> >
> > Any advice?
>
> This question was asked several weeks ago, and Anno Siegel had a most
> elegant solution. I googled for it but couldn't find.
I am honored, but I think Google is right. I don't remember this
particular problem from the recent past.
I have tried a couple of variants of Ilya's suggestion (using an index
array), but nothing came up to write home (to clpm) about.
Anno
--
If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers.
A. Sinan Unur
news:e0fb2n$1kpd$1...@agate.berkeley.edu:
> [A complimentary Cc of this posting was sent to
> A. Sinan Unur <1u...@llenroc.ude.invalid>], who wrote in article
> <Xns9795CB63AB7D...@127.0.0.1>:
>> You need to work a little on explaining the problem and algorithm.
>> Neither the code snippet above nor your verbal description makes any
>> sense to me
>
> I'm afraid the problem is on your side. The explanation-by-code looks
> absolutely clear to me.
Well, I see now that I am the only one who was perplexed by this. Sorry.
David Formosa (aka ? the Platypus)
>
> David Formosa (aka ? the Platypus) wrote:
[...]
>> I quickly worked out one way to do this, no guarties as to effeceny.
>>
>> sub closefor (&$@) {
>> my $sub = shift;
>> my $range = shift;
>>
>> return sub {
>> for my $i (0..$range){
>> $sub->($i,@_)
>> }
>> }
>> }
>>
>> sub mulitloop (&@) {
>> my $sub = shift;
>> for (@_) {
>> my $oldsub = $sub;
>> $sub = closefor {$oldsub->(@_)} $_;
>> }
>> $sub->();
>> }
[...]
>> mulitloop {
>> my $sum = 0;
>> my $product = 1;
>> for (my $i; $i<=@#_; $i++) {
>> $sum += $_[$i];
>> $product *= $f_raa->[$i]->[$_[$i]];
>> }
>> $prob_ra->[$sum] += $product;
>> } @$n_ra;
> You know as clever and elegant as this method is, it actually runs
> significantly than my original ugly cut-and-paste style,
Yeah after thinking about it the above code does some things
redundently and actually causes perl to do alot of extra needless
work. This should be a little more effecent.
sub calc_prob_ra ($$$;@) {
my $sum = shift;
my $prod = shift;
my $depth = shift;
if (@_) {
my $n = shift;
calc_prob_ra($sum+$n,$prod * $f_aa->[$depth]->[$_],$depth+1,@_)
for (0..$n);
} else {
$prob_ra->[$sum] += $prod;
}
}
calc_prob_ra(0,1,1,@$n_ra);
There should be signifigently less overhead in this case (I've
eleminated a needless loop, and all the closure creation and
derefrencing).
[...]
> Anyway, I'm going to keep this code for further use and some later
> date, but I eventyually went with John Krahn eval method posted
> above.
I should bench test Mr Krahn's eval method vs my new method. But Its
to late and I'm far to tired.
Tad McClellan
> Jim Gibson <jgi...@mail.arc.nasa.gov> wrote in comp.lang.perl.misc:
>> In article <1143679874.6...@u72g2000cwu.googlegroups.com>,
>> Jacob JKW <jaco...@yahoo.com> wrote:
>> > decide at run time to have how nested levels to go
>> This question was asked several weeks ago, and Anno Siegel had a most
>> elegant solution. I googled for it but couldn't find.
>
> I am honored, but I think Google is right. I don't remember this
> particular problem from the recent past.
Maybe Jim was thinking of the plain old "pointer walk" that I
posted in:
Message-Id: <slrne24dqv...@magna.augustmail.com>
??
--
Tad McClellan SGML consulting
ta...@augustmail.com Perl programming
Fort Worth, Texas
Anno Siegel
> [A complimentary Cc of this posting was sent to
> A. Sinan Unur
> <1u...@llenroc.ude.invalid>], who wrote in article
> <Xns9795CB63AB7D...@127.0.0.1>:
> > You need to work a little on explaining the problem and algorithm.
> > Neither the code snippet above nor your verbal description makes any
> > sense to me
>
> I'm afraid the problem is on your side. The explanation-by-code looks
> absolutely clear to me.
>
> Looks like there is a multi-dimensional array of unknown-in-advance
> dimension. It is known that it is "rectangular"; the sizes are stored
> in another vector (one size per dimension).
I agree that the code made pretty much clear what was wanted. However,
I would describe the situation in exactly the opposite terms:
We have an array of *known* dimension 2 (it's an array of arrays). Its size
is not known in advance. Similarly, is *not* rectangular, but ragged. Each
sub-array has its individual length, also not known until run-time. Storing
the sizes in an extra vector wouldn't be necessary since Perl arrays know
their length.
> One wants a CONVENIENT way to run through the elements of this array.
>
> One hint to OP: since you do not know the dimension at compile
> time, you cannot be sure that the index of 1st,2nd,3rd etc
> dimensions is $k, $l, $m etc. So the only solution is to have the
> running index to be an array too: $I[0], $I[1], $I[3] etc.
>
> This more or less immediately suggests a possible solution...
The core of that solution would be a combinatorial routine (once again)
that guides the multi-index through all possible combinations, given a
concrete array of arrays. Here is a possible solution. The
index-switching routine is next_idx(). It takes two arrayrefs, the
first of which is the multi-index which will be modified. The second
argument is the array of arrays we're working on, it tells how far each
index may count. It returns true, except when the multi-index has
overflown and is all-zeroes again.
I have changed some variables from array-refs to arrays.
use List::Util qw( sum);
my @f_raa = ( [ 1, 2, 3], [ 1, 2, 3, 4, 5], [ 1, 2] ); # for example
my @prob_ra; # The result
my @idx = ( 0) x @f_raa; # the multi-index, starting at (0, 0, 0)
while ( 1 ) {
my $prod = 1;
$prod *= $f_raa[ $_]->[ $idx[ $_]] for 0 .. $#idx;
$prob_ra[ sum @idx] += $prod;
last unless next_idx( \ @idx, \ @f_raa);
}
sub next_idx {
my ( $idx, $f_raa) = @_;
my @max = map $#$_, @$f_raa;
$_ < shift @max and return ++ $_ or $_ = 0 for @$idx;
return 0;
}
__END__
Dr.Ruud
> the plain old "pointer walk" that I
> posted in:
>
> Message-Id: slrne24dqv...@magna.augustmail.com
Why don't you format that as a URI?
news:slrne24dqv...@magna.augustmail.com
See also: http://www.w3.org/Addressing/
--
Affijn, Ruud
"Gewoon is een tijger."
Tad McClellan
> Tad McClellan schreef:
>
>> the plain old "pointer walk" that I
>> posted in:
>>
>> Message-Id: slrne24dqv...@magna.augustmail.com
>
> Why don't you format that as a URI?
Laziness (the bad kind).
I triple-clicked and middle-clicked and it was copied.
timkazner
Not sure if this is what you are trying to do
but. Some redundency left in for clarity and
its untested (not debugged).
my $isize = 5;
my $jsize = 20;
my $ksize = 60;
my %ihash = ();
my %jhash = ();
my %khash = ();
my @f_raa = (\%ihash, \%jhash, \%khash);
# assign i,j,k hash data
for (0..$isize) { $ihash{$_} = $_;}
for (0..$jsize) { $jhash{$_} = $_;}
for (0..$ksize) { $khash{$_} = $_;}
my @n_ra = ($isize, $jsize, $ksize);
or
#@n_ra = (keys %ihash, keys %jhash, keys %khash);
for (my $i = 0; $i<=$n_ra[0]; $i++) {
for (my $j = 0; $j<=$n_ra[1]; $j++) {
for (my $k = 0; $k<=$n_ra[2]; $k++) {
$prob_ra{$i+$j+$k} += (
$f_raa[0]->{$i} *
$f_raa[1]->{$j} *
$f_raa[2]->{$k} *
);
}
}
}
timkazner
[snipped]
Forgot the output (if its necessary)
my $isize = 5;
my $jsize = 20;
my $ksize = 60;
my %prob_ra = ();
my %ihash = ();
my %jhash = ();
my %khash = ();
my @f_raa = (\%ihash, \%jhash, \%khash);
# assign i,j,k hash data
for (0..$isize) { $ihash{$_} = $_;}
for (0..$jsize) { $jhash{$_} = $_;}
for (0..$ksize) { $khash{$_} = $_;}
my @n_ra = ($isize, $jsize, $ksize);
or
#@n_ra = (keys %ihash, keys %jhash, keys %khash);
for (my $i = 0; $i<=$n_ra[0]; $i++) {
for (my $j = 0; $j<=$n_ra[1]; $j++) {
for (my $k = 0; $k<=$n_ra[2]; $k++) {
$prob_ra{$i+$j+$k} += (
$f_raa[0]->{$i} *
$f_raa[1]->{$j} *
$f_raa[2]->{$k} *
);
}
}
}
foreach my $key (keys %prob_ra) {
print "$key \t = ".$prob_ra{$key}."\n";
}
timkazner
I've re-read John Krahn's posted code using eval
for dynamic code generation. To generate the OP's
source, it is broken down into the nested for loops
and an inner operation asignment.
Ok I understand it now. Thanks!