Nested for loops?

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Nested for loops?

Postby Ended » Tue Oct 16, 2007 7:13 pm UTC

So, this is something I've come up against in a few contexts now. Suppose I have an array x[N] which represents position in N-dimensional space. So x is type double, say. Is there an efficient/clean way to iterate the vector x through (a discretised and bounded subset of) RN?

I can do (in Java) something like:

Code: Select all

final int N = 3;
double x[] = new double[N];
double h = 0.1;
double bound = 1;

for(x[0]=0 ; x[0]<bound ; x[0]+=h)
{
  for(x[1]=0 ; x[1]<bound ; x[1]+=h)
  {
     for(x[2]=0 ; x[2]<bound ; x[2]+=h)
     {
       doStuff(x);
     }
  }
}

But this is ugly. More importantly, I want to be able to specify N at run-time.

Any ideas? I'm looking to do this in C/Java, but I'd appreciate suggestions for other languages where it might be easier to do this type of thing.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

User avatar
rrwoods
Posts: 1509
Joined: Mon Sep 24, 2007 5:57 pm UTC
Location: US

Re: Nested for loops?

Postby rrwoods » Tue Oct 16, 2007 7:54 pm UTC

Code: Select all

public class StepVector implements Iterable<List<Double>>
{
    private java.util.List<Double> position;
    private double startValue;
    private double stepSize;
    private double endValue;
   
    public StepVector(int dimension, double startValue, double stepSize, double endValue)
    {
        this.position = new ArrayList();
        for(int i = 0; i < dimension; i++)
            this.position.add(startValue);
       
        this.startValue = startValue;
        this.stepSize = stepSize;
        this.endValue = endValue;
    }
   
    public Iterator<List<Double>> iterator()
    {
        return new Iterator<List<Double>> ()
        {
            public void remove()
            {
                throw new UnsupportedOperationException();
            }
           
            public List<Double> next()
            {
                for(int i = this.dimension - 1; i >= 0; i--)
                {
                    double newValue = this.position.get(i) + stepValue;
                    if(newValue > endValue)
                    {
                        this.position.set(i, startValue);
                    }
                    else
                    {
                        this.position.set(i, newValue);
                        break;
                    }
                }
                return this.position.clone();
            }
           
            public boolean hasNext()
            {
                for(int i = 0; i < this.dimension; i++)
                    if(this.position.get(i) + stepValue < endValue)
                        return true;
               
                return false;
            }
        };
    }
}

I don't know whether this actually compiles or works, because I don't have a java compiler on this machine or the time to compile it, but this should be tweakable.
31/M/taken/US
age/gender/interest/country

Belial wrote:The sex card is tournament legal. And I am tapping it for, like, six mana.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Nested for loops?

Postby Cosmologicon » Tue Oct 16, 2007 9:39 pm UTC

While I can only imagine that rrwoods' solution is good, here's how I often go about it (This is in C++, but I understand Java is similar):

Code: Select all

  const int N = 3;
  double x[N], h = 0.1, bound = 0.99;
  int j;
  for (j = 0; j < N; ++j) x[j] = 0.;
  do {
    doStuff(x);
    for (j = N-1; (x[j] += h) >= bound and j >= 0; x[j--] = 0);
  } while (j >= 0);

See? It's sort of like treating x as an N-digit number and incrementing it. This should be effectively equivalent to your code, but I changed bound to 0.99, because of floating-point comparison issues.

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: Nested for loops?

Postby Ended » Tue Oct 16, 2007 10:43 pm UTC

rrwoods: cool, it compiled pretty easily actually, just a couple of typos, although I had to change the fields to public static or the Iterator class couldn't see them (you could probably pass them or something though). Worked great. Also, +1 props for the compiler-less coding.

Cosmologicon: yeah, this was the sort of thing I was expecting, I knew there had to be a way of looping in that way but couldn't figure it out.

Thanks guys! Both solutions will be useful in different contexts.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

User avatar
rrwoods
Posts: 1509
Joined: Mon Sep 24, 2007 5:57 pm UTC
Location: US

Re: Nested for loops?

Postby rrwoods » Wed Oct 17, 2007 12:59 pm UTC

Cosmologicon wrote:It's sort of like treating x as an N-digit number and incrementing it.

Yeah, that's what I was originally thinking of doing as well, but couldn't figure a way to implement it.

Ended wrote:cool, it compiled pretty easily actually, just a couple of typos, although I had to change the fields to public static or the Iterator class couldn't see them (you could probably pass them or something though). Worked great. Also, +1 props for the compiler-less coding.

Woot! Although I like Cosmologicon's solution better if it's a one-of project.
31/M/taken/US
age/gender/interest/country

Belial wrote:The sex card is tournament legal. And I am tapping it for, like, six mana.

User avatar
Nimz
Posts: 580
Joined: Thu Aug 02, 2007 9:49 am UTC
Location: the origin

Re: Nested for loops?

Postby Nimz » Thu Oct 18, 2007 9:57 pm UTC

This sounds similar to something I'm trying to do. I've been using nested while loops, but maybe for would be simpler.

What I am trying to do is iterate k vectors through a discretised (and clearly bounded - each coordinate is either 0 or 1) subset of RN in such a way that the vectors are distinct from each other. I have been representing the vectors as integers from 0 to 2N+1-1, each mapped lexicographically to base 10 numbers between 0 to (10N+1-1)/9. Clearly there is room for improvement here - it's been years since I last programmed in C++ (when I was taking an intro course in C++) and I haven't really done anything serious in other languages.

I've written C++ code that compiles and sort of gives the results I want, but I'm wondering if there's a better way than nesting 14 while loops when I'm iterating 16-2 = 14 vectors in R5. Ideally I would like something that can easily extend to 2N-1 vectors in RN, where I can specify N at runtime. Here's what I have, with alot of repetitive stuff omitted (all variables are of type int):

Code: Select all

a0 = 0;
a1 = 1;
a2 = 2;
b0 = 0;
b1 = 1;
b2 = 10;
while(a2 <= 18)
{
  a3 = a2+1;
  while(a3 <= 19)
  {
   ...
        a15 = a14+1;
        while(a15 <= 31)
        {
           b2 = lex(a2);
           b3 = lex(a3);
           ...
           b15 = lex(a15);
           doStuff()
           a15++;
        }
        a14++;
     ...
     a3++;
  }
  a2++;
}
I took advantage of some symmetries to fix a0 and a1 (symmetries that will appear in general), so it really is 14 vectors being iterated in R5, not 16.

For what it's worth, my first attempt at something similar to this is in this thread. The "do stuff" stage is a bit different now, though.

0SpinBoson
Posts: 92
Joined: Thu Oct 04, 2007 5:28 pm UTC

Re: Nested for loops?

Postby 0SpinBoson » Thu Oct 18, 2007 10:10 pm UTC

Could you clarify a little bit? I got lost in your notation

User avatar
Nimz
Posts: 580
Joined: Thu Aug 02, 2007 9:49 am UTC
Location: the origin

Re: Nested for loops?

Postby Nimz » Fri Oct 19, 2007 2:28 am UTC

Sorry. I haven't been expressing myself very well, even to myself, today. I cobbled together some code that works. The sample code I gave is an excerpt of it. I'm just wondering if there is a more efficient way to do what I want to do.

What I want to do: loop through every combination of k selected vectors on a subset of RN that contains 2N vectors.

How my code does what it does: it assigns each vector a number from 0 to 2N-1. Nested while loops (k of them) are used to do the iterating. As it is, I need to increase the number of nested while loops if I want more vectors (up to 2N-1, of course - more vectors and the situation is the complement of a situation with fewer vectors.) A simple example of my while loop nesting:

Code: Select all

a = 1;
while(a < 4)
{
   b = a+1;
   while(b < 5)
   {
      c = b+1;
      while(c < 6)
      {
         do_stuff(a,b,c);
         c++;
      }
      b++;
   }
   a++;
}
will do stuff to (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,4), (2,3,5), (2,4,5), and (3,4,5).

What I want to know: is there a better way to do this? More specifically, would for be better than while? And is there a more general way to represent the vectors so that I don't have to rewrite code when I go to a higher dimension or increase the number of selected vectors? Since I have my code working right now, I don't need to know for now, but maybe for future reference.
LOWA

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Nested for loops?

Postby Cosmologicon » Fri Oct 19, 2007 3:29 am UTC

I usually consider the subsets to be permutations of true/false values, so I use the STL functions prev_permutation and next_permutation. I don't know what I'd use in another language besides C++. I bet Java has something just as useful:

Code: Select all

  const int n = 5, k = 3;
  std::vector<bool> b(n);
  for (int j = 0; j < n; ++j) b[j] = j < k;
  do {
    std::vector<int> a;
    for (int j = 0; j < n; ++j) if (b[j]) a.push_back(j);
    do_stuff(a);
  } while (std::prev_permutation(b.begin(), b.end()));

User avatar
Geekthras
3) What if it's delicious?
Posts: 529
Joined: Wed Oct 03, 2007 4:23 am UTC
Location: Around Boston, MA

Re: Nested for loops?

Postby Geekthras » Fri Oct 19, 2007 5:10 am UTC

I might be completely misunderstanding, but:

Code: Select all

public void recursiveLOL(int depth) {
   if(depth==N) {
      dostuff(x);
   } else {
      for(x[depth]=0;x[depth]<1;x[depth]+=h) {
         recursiveLOL(depth+1);
      }
   }
}

With x, N, h instance variables.
Or some such thing. It's 1 AM so this probably off, but is tweakable.


Of course this only works up to like 256-d or something in Java. ;p
Wait. With a SPOON?!

User avatar
Pathway
Leon Sumbitches...?
Posts: 647
Joined: Sun Oct 15, 2006 5:59 pm UTC

Re: Nested for loops?

Postby Pathway » Fri Oct 19, 2007 7:27 am UTC

You could try ArrayLists and Iterators. They can provide the same functionality as arrays and for loops but without the need to specify numbers of items.

I'm thinking--never mind, I just looked at rrwoods' code and it's what I was going to say, except much better developed.
SargeZT wrote:Oh dear no, I love penguins. They're my favorite animal ever besides cows.

The reason I would kill penguins would be, no one ever, ever fucking kills penguins.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests