dynamic number of nested loops

[Allan Bruce]

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

 

[Eric Sosman]

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 += 1;
if (digit < limit)
break;
digit = 0;
}
if (i == digit.length)
break; // finished the cycle
}

In your case you'd probably want to use each `digit' as
the index into an array of variable or derivative values,
and the `limit' 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;

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 = temp % steps;
temp /= steps;
}

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.)

 

[Eric Sosman]

[...]
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 = temp % steps;

.... 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."

 

[Joona I Palaste]

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.

 

[Roedy Green]

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

 

[Tor Iver Wilhelmsen]

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.