Arbitrarily Many Nested Loops

[Jacob JKW]

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?


Many Thanks,
J.

 

[A. Sinan Unur]

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?

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 <[email protected]>
(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 complimentary Cc of this posting was sent to
A. Sinan Unur

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:ari's forvec(); might be a little bit
heavy-weight solution, but maybe then you will find some use for
other functions in Math:ari too. ;-)

 

[John W. Krahn]

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.

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

 

[Jacob JKW]

[A complimentary Cc of this posting was sent to
A. Sinan Unur

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.

I was definitely a bt lacadaisical in my proofreading efforts. What I
*should* have written was:
But that's obviously messy and more imprtantly I'd like to be able to
decide at run time how many nested levels I'll need.

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:ari's forvec(); might be a little bit
heavy-weight solution, but maybe then you will find some use for
other functions in Math:ari too. ;-)

Self-promote much? ;-)

 

[Jacob JKW]

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.

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;

I made a few synactical changes but it worked out beautifully. Thank
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.)

Do you think if I became agraphic I could become as good a programmer
as you?

 

[Ron Savage]

On Thu, 30 Mar 2006 13:54:58 +1000, Jacob JKW wrote:

Hi Jacob

Glad to see you obtained a solution.

Just for the record, this was discussed in a book by the Australianprogrammer
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]

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.

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;

--

You know as clever and elegant as this method is, it actually runs
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]

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.

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;

You know, I initially shied away from this method just because I've
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]

On Thu, 30 Mar 2006 13:54:58 +1000, Jacob JKW wrote:

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

Thanks. Always on the lookout for a good read. I'll check it out.

 

[Anno Siegel]

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

 

[A. Sinan Unur]

[A complimentary Cc of this posting was sent to

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.

Sinan
--
A. Sinan Unur <[email protected]>
(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

 

[Tad McClellan]

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: <[email protected]>

??

 

[Anno Siegel]

[A complimentary Cc of this posting was sent to
A. Sinan Unur

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__

Anno

 

[Dr.Ruud]

Tad McClellan schreef:

the plain old "pointer walk" that I
posted in:

Message-Id: (e-mail address removed)

Why don't you format that as a URI?


See also: http://www.w3.org/Addressing/

 

[Tad McClellan]

Tad McClellan schreef:


Why don't you format that as a URI?

Laziness (the bad kind).

I triple-clicked and middle-clicked and it was copied.

 

[Tim Kazner]

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?


Many Thanks,
J.

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} *
);
}
}
}

 

[Tim Kazner]

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?


Many Thanks,
J.

Not sure if this is what you are trying to do
but. Some redundency left in for clarity and
its untested (not debugged).

[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";
}

 

[Tim Kazner]

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?


Many Thanks,
J.

Not sure if this is what you are trying to do
but. Some redundency left in for clarity and
its untested (not debugged).

[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";
}

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!