dynamic number of nested loops

Discussion in 'Java' started by Allan Bruce, Jul 1, 2004.

  1. Allan Bruce

    Allan Bruce Guest

    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
    Allan Bruce, Jul 1, 2004
    #1
    1. Advertising

  2. Allan Bruce

    Eric Sosman Guest

    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 += 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, Jul 1, 2004
    #2
    1. Advertising

  3. Allan Bruce

    Eric Sosman Guest

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

    --
    Eric Sosman, Jul 1, 2004
    #3
  4. Allan Bruce <> 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 () ------------- Finland --------\
    \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
    "Roses are red, violets are blue, I'm a schitzophrenic and so am I."
    - Bob Wiley
    Joona I Palaste, Jul 1, 2004
    #4
  5. Allan Bruce

    Roedy Green Guest

    On Thu, 1 Jul 2004 18:50:40 +0100, "Allan Bruce"
    <> 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.
    Roedy Green, Jul 2, 2004
    #5
  6. "Allan Bruce" <> 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.
    Tor Iver Wilhelmsen, Jul 3, 2004
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Porthos
    Replies:
    3
    Views:
    474
    Joris Gillis
    Feb 7, 2005
  2. SplaTTer
    Replies:
    2
    Views:
    369
    SplaTTer
    Jul 2, 2003
  3. viza

    break or continue out of nested loops

    viza, Jul 16, 2003, in forum: C Programming
    Replies:
    5
    Views:
    1,004
    sunil
    Jul 17, 2003
  4. Klaas Vantournhout

    unkown number of nested for loops

    Klaas Vantournhout, Sep 21, 2006, in forum: C Programming
    Replies:
    3
    Views:
    320
    Lew Pitcher
    Sep 21, 2006
  5. Me
    Replies:
    2
    Views:
    229
Loading...

Share This Page