Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > dynamic number of nested loops

Reply
Thread Tools

dynamic number of nested loops

 
 
Allan Bruce
Guest
Posts: n/a
 
      07-01-2004
I have a program which I need to be able to produce all the possible states
from a given set of variables. This requires me to have a variable number
of nested loops, depending on how many derivativest the user specifies.
What is the best way to do this? I was considering limiting the number of
derivatives and using if statements but this is quite messy. Am I
describing my problem clear enough? If not then look below for an example
problem.

A state in my system holds the current values of my world variables. Each
variable has a number of derivatives specified by the user, and each
derivative has a number of possible values specified by the user. For
example, one simple problem is this:

3 variables: V, qi, qo
V has 3 derivatives, and qi/qo both have only 2
the first derivative of each variable can have 9 possible values, and the
rest of the derivatives can have 5

For this system there are 9x5x5 possible values for V (=225)
there are 9x5 possible values for qo (=45)
there are 9x5 possible values for qi (=45)

therefore there are 225x45x45 possible states in the system (=455625)

Can anybody shed some light as to how I would approach this problem?
Thanks
Allan


 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      07-01-2004
Allan Bruce wrote:
> I have a program which I need to be able to produce all the possible states
> from a given set of variables. This requires me to have a variable number
> of nested loops, depending on how many derivativest the user specifies.
> What is the best way to do this? I was considering limiting the number of
> derivatives and using if statements but this is quite messy. Am I
> describing my problem clear enough? If not then look below for an example
> problem.
>
> A state in my system holds the current values of my world variables. Each
> variable has a number of derivatives specified by the user, and each
> derivative has a number of possible values specified by the user. For
> example, one simple problem is this:
>
> 3 variables: V, qi, qo
> V has 3 derivatives, and qi/qo both have only 2
> the first derivative of each variable can have 9 possible values, and the
> rest of the derivatives can have 5
>
> For this system there are 9x5x5 possible values for V (=225)
> there are 9x5 possible values for qo (=45)
> there are 9x5 possible values for qi (=45)
>
> therefore there are 225x45x45 possible states in the system (=455625)
>
> Can anybody shed some light as to how I would approach this problem?


Use one loop, plus an array of "index values" that keep
track of where you are. Here's a tiny example that counts
from 0:00 to 2:59, using a different array element for each
of the three digits:

int[] digit = { 0, 0, 0}; // units, tens, sixties
final int[] limit = { 10, 6, 3 };
for (; {
do_your_thing(digit);

int i;
for (i = 0; i < digit.length; ++i) {
digit[i] += 1;
if (digit[i] < limit[i])
break;
digit[i] = 0;
}
if (i == digit.length)
break; // finished the cycle
}

In your case you'd probably want to use each `digit[i]' as
the index into an array of variable or derivative values,
and the `limit[i]' would be the length of the corresponding
array. This sort of adaptation should be straightforward.

Another approach is to do an ordinary count from zero to
455624 (in your example), and then derive the digits with
division and remainder:

final int[] steps = { 225, 45, 45 };
long limit = 1;
for (int i = 0; i < steps.length; ++i)
limit *= steps[i];

int[] digit = new int[ steps.length ];
for (long index = 0; index < limit; ++index) {
long temp = index;
for (int i = 0; i < steps.length; ++i) {
digit[i] = temp % steps[i];
temp /= steps[i];
}

do_your_thing(digit);
}

What you're really trying to do here is count in a mixed-
radix number system. See D.E. Knuth "The Art of Computer
Programming, Volume II: Seminumerical Algorithms" for fancier
manipulations than these. (When Volume 4 comes out -- some
pre-print proofs are on his Web site -- it'll probably show
some even slicker ways of doing this sort of thing.)

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      07-01-2004
Eric Sosman wrote:
> [...]
> int[] digit = new int[ steps.length ];
> for (long index = 0; index < limit; ++index) {
> long temp = index;
> for (int i = 0; i < steps.length; ++i) {
> digit[i] = temp % steps[i];


.... and you can tell I'm at heart an unreconstructed C
programmer who forgets how picky Java is about casts.
"Pseudocode, yeah, dat's it, I was just writin' pseudocode."

--
(E-Mail Removed)

 
Reply With Quote
 
Joona I Palaste
Guest
Posts: n/a
 
      07-01-2004
Allan Bruce <(E-Mail Removed)> scribbled the following:
> I have a program which I need to be able to produce all the possible states
> from a given set of variables. This requires me to have a variable number
> of nested loops, depending on how many derivativest the user specifies.
> What is the best way to do this? I was considering limiting the number of
> derivatives and using if statements but this is quite messy. Am I
> describing my problem clear enough? If not then look below for an example
> problem.


> A state in my system holds the current values of my world variables. Each
> variable has a number of derivatives specified by the user, and each
> derivative has a number of possible values specified by the user. For
> example, one simple problem is this:


> 3 variables: V, qi, qo
> V has 3 derivatives, and qi/qo both have only 2
> the first derivative of each variable can have 9 possible values, and the
> rest of the derivatives can have 5


> For this system there are 9x5x5 possible values for V (=225)
> there are 9x5 possible values for qo (=45)
> there are 9x5 possible values for qi (=45)


> therefore there are 225x45x45 possible states in the system (=455625)


> Can anybody shed some light as to how I would approach this problem?


I had a similar problem when I had to write code to enumerate all the
possible winner combinations for a game where 2 to 6 matches are played,
and each match has a separate set of contestants. As unbelievable as
this may sound, this was production code - not homework. I ended up
solving the problem by using recursion. I wrote a method that only had
one loop, but this method called itself from inside the loop. To
avoid infinite recursion I used a feature I've invented myself, but a
lot of other people have no doubt also invented - I passed a parameter
to the method telling it how deep it was in the recursion, and if it
was going too deep, it stopped the recursion.

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"Roses are red, violets are blue, I'm a schitzophrenic and so am I."
- Bob Wiley
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      07-02-2004
On Thu, 1 Jul 2004 18:50:40 +0100, "Allan Bruce"
<(E-Mail Removed)> wrote or quoted :

>This requires me to have a variable number
>of nested loops,


One way you could do this is to use a recursive method containing a
loop. Think of the sort of code you use to traverse the directory
tree of a disk. Each level passes enough history to the next level
down.

The nice thing about recursion is it automatically keeps track of
where you were at each level.

Another approach that would come easily to an ex-Forth programmer is
to think about how you would simulate 3-nested for loop with just a
pushdown lifo stack and single while loop. see
http://mindprod.com/jgloss/stack.html

See also http://mindprod.com/jgloss/combination.html
http://mindprod.com/jgloss/permutation.html

--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
 
Reply With Quote
 
Tor Iver Wilhelmsen
Guest
Posts: n/a
 
      07-03-2004
"Allan Bruce" <(E-Mail Removed)> writes:

> I have a program which I need to be able to produce all the possible states
> from a given set of variables. This requires me to have a variable number
> of nested loops, depending on how many derivativest the user specifies.
> What is the best way to do this?


Use a stack of sorts to push your state on whenever you go "deeper",
and pop from it when "going up" again.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
unkown number of nested for loops Klaas Vantournhout C Programming 3 09-21-2006 05:19 PM
Loops with loops using html-template Me Perl Misc 2 01-12-2006 05:07 PM
nested loops and conditional statements Porthos XML 3 02-07-2005 08:47 PM
break or continue out of nested loops viza C Programming 5 07-17-2003 04:04 AM
compacting similar nested for loops SplaTTer C++ 2 07-02-2003 09:16 PM



Advertisments