Re: Arbitrarily Many Nested Loops
- From: anno4000@xxxxxxxxxxxxxxxxxxxxxxx (Anno Siegel)
- Date: 30 Mar 2006 16:54:15 GMT
Ilya Zakharevich <nospam-abuse@xxxxxxxxx> wrote in comp.lang.perl.misc:
[A complimentary Cc of this posting was sent to
A. Sinan Unur
<1usa@xxxxxxxxxxxxxxxxxxx>], who wrote in article
<Xns9795CB63AB7DAasu1cornelledu@xxxxxxxxx>:
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
--
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.
.
- References:
- Arbitrarily Many Nested Loops
- From: Jacob JKW
- Re: Arbitrarily Many Nested Loops
- From: A. Sinan Unur
- Re: Arbitrarily Many Nested Loops
- From: Ilya Zakharevich
- Arbitrarily Many Nested Loops
- Prev by Date: Re: Arbitrarily Many Nested Loops
- Next by Date: Re: Where to put Settings-Variables?
- Previous by thread: Re: Arbitrarily Many Nested Loops
- Next by thread: Re: Arbitrarily Many Nested Loops
- Index(es):
Relevant Pages
|
