By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,386 Members | 1,676 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,386 IT Pros & Developers. It's quick & easy.

A Quesiton about nesting for loops..

P: n/a
I have a need to make an applicaiton that uses a variable number of nested
for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?

Jul 19 '05 #1
Share this Question
Share on Google+
15 Replies


P: n/a
In comp.lang.c++
"JustSomeGuy" <no**@nottelling.com> wrote:
I have a need to make an applicaiton that uses a variable number of nested
for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


What is the "larger" problem you are trying to solve? In over 20 years,
I've never needed to do what you're doing.
Jul 19 '05 #2

P: n/a
N dimensional math.

"Bruce" <br***@nospam.com> wrote in message
news:3f***************@news.houston.sbcglobal.net. ..
In comp.lang.c++
"JustSomeGuy" <no**@nottelling.com> wrote:
I have a need to make an applicaiton that uses a variable number of nestedfor loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


What is the "larger" problem you are trying to solve? In over 20 years,
I've never needed to do what you're doing.

Jul 19 '05 #3

P: n/a
[Do not (repeated for your convenience, DO NOT) top-post, rearranged]

On Wed, 17 Sep 2003 21:19:17 -0600, "JustSomeGuy" <no**@nottelling.com> wrote:
"Bruce" <br***@nospam.com> wrote in message
news:3f***************@news.houston.sbcglobal.net ...
In comp.lang.c++
"JustSomeGuy" <no**@nottelling.com> wrote:
>I have a need to make an applicaiton that uses a variable number ofnested >for loops.
>
>for now I'm using a fixed number:
>
>for (z=0; z < Z; ++z)
> for (y=0; y < Y; ++y)
> for (x=0; x < X; ++x)
>
>
>The thing is there could be less or more nested loops necessary.
>How can I write this such that the number of for loops is a variable?


What is the "larger" problem you are trying to solve? In over 20 years,
I've never needed to do what you're doing.


N dimensional math.


Try to be more concrete. Give a concrete example of a problem where
it seems that you need a variable number of loops. Most such cases
are not amenable to direct (simple-minded) implementation as computer
programs, due to the extremely large number of steps and/or extremely
large values typically involved; e.g., check out Ackermann's function
(which also illustrates one way of achieving dynamic nesting of loops).

Hth.

- Alf

Jul 19 '05 #4

P: n/a
> I have a need to make an applicaiton that uses a variable number of nested
for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)

The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


Hmm. Before you even vary the number of dimensions, observe that your lines
all look the same.

When faced with duplication, if you can find a way to make it similar, then
make it the same, you can often introduce an abstraction that makes the
design more extensible.

for (int x=0; x < Z; ++x)
for (int x=0; x < Y; ++x)
for (int x=0; x < X; ++x)

Now the inner statements can't see the x from the outer statements. Pretend
they can, and keep going.

Now that the statements look similar, make them the same. Put them in a
function, and call the function recursively:

void loop (int y) {
for (int x=0; x < limit; ++x)
loop(x);

Now you have only one for loop. To finish the design, add a way to detect
how deep the recursion goes, and some way to stop at a given depth.

void loop (int y, int depth) {
if (depth > max) return;
for (int x=0; x < limit; ++x)
loop(x, depth+1);

Get the code - whatever it does - to fully work now, before going to an
arbitrary number of dimensions.

So, now we need some system to make X depend on the depth, and to index
whatever we are indexing variantly.

void loop (int y, int depth) {
if (depth > max) return;
for (int x=0; x < limits[depth]; ++x)
loop(x, depth+1);

I don't know what your variable dimensioned object looks like, so you'l have
to take it from here.

But note that duplication removal - even such that looked absurd at first -
gave us the abstraction we sought, almost as a by-product.

BTW I'd create a multiple-dimension array as a sparse array, using the
indices hashed together to form unique keys. For example,

std::map<string, string> aMap;
aMap["7,12,0,0,1"] = "whatever";

Now to iterate, loop() would add its indices to the end of a string, and
pass that string to loop.

--
Phlip
http://www.c2.com/cgi/wiki?TestFirstUserInterfaces
Jul 19 '05 #5

P: n/a
JustSomeGuy <no**@nottelling.com> wrote in message
news:bk**********@nserve1.acs.ucalgary.ca...
N dimensional math.


I've done some N-dimensional maths before (e.g., simplex optimization in N
dimensions, where N varies at run-time), but I didn't need an explicit
compile-time loop for each dimension. I had at most two nested loops, in
which one of them iterates 0 to N-1. Maybe your problem is harder, but I'd
be surprised if it couldn't be done without a 'for' loop for each dimension.

If you give a more specific example of what you want to do, I'm sure someone
can suggest how to do it.

DW

Jul 19 '05 #6

P: n/a

JustSomeGuy <no**@nottelling.com> wrote in message
news:bk***********@nserve1.acs.ucalgary.ca...
I have a need to make an applicaiton that uses a variable number of nested
for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


Call a function containing a single loop recursively.

-Mike

Jul 19 '05 #7

P: n/a
"JustSomeGuy" <no**@nottelling.com> wrote in message
news:bk***********@nserve1.acs.ucalgary.ca...
I have a need to make an applicaiton that uses a variable number of nested
for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


This one was actually a nice little challenge :-)
Here is my implementation (not the fastest one or anything, but seams to
work just fine... under OpenBSD and GCC 2.96 i think).
Hope this helps you. If you need more explanation of how this code works,
let me know, i will be happy to explain.
Notice the stack of for_loop objects is reversed, meaning the top entry
represents the most outer loop, and deeper down the stack => deeper the
nested for loop... recursion rocks!

#include <stack>
#include <string>
#include <iostream>
using namespace std;

class for_loop {
public:
for_loop(const string& name = "", int reps = 0)
: _name(name), _reps(reps), _current(0) {}
int at(void) { return _current; }
void tick(void) { ++_current; }
bool done(void) { return _current == _reps; }
string name(void) { return _name; }

private:
string _name;
int _reps;
int _current;
};

void magic(stack<for_loop> loops, stack<for_loop> outer) {
for_loop temp = loops.top();
loops.pop();

if(!loops.empty()) {
for_loop loop = temp;
for_loop backup = temp;

do {
cout
<< loop.name()
<< ", "
<< loop.at()
<< ", "
<< outer.size()
<< endl;

outer.push(loop);
magic(loops, outer);
outer.pop();

loop.tick();
} while(!loop.done());

loops.push(backup);
} else {
for_loop loop = temp;
for_loop backup = temp;

do {
cout
<< loop.name()
<< ", "
<< loop.at()
<< ", "
<< outer.size()
<< endl;
loop.tick();
} while(!loop.done());
}
}

int main(int args, char **argv) {
for_loop loop0(" loopW", 2);
for_loop loop1(" loopX", 4);
for_loop loop2(" loopY", 3);
for_loop loop3("loopZ", 2);

stack<for_loop> loops;
stack<for_loop> outer;

loops.push(loop0);
loops.push(loop1);
loops.push(loop2);
loops.push(loop3);

magic(loops, outer);

return 0;
}

And the output is:

loopZ, 0, 0
loopY, 0, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopY, 1, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopY, 2, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopZ, 1, 0
loopY, 0, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopY, 1, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopY, 2, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3


Jul 19 '05 #8

P: n/a
ALso notice that at ever level, you get the loop you are iterating, and the
stack of all loops above you.
"Marcin Vorbrodt" <mv*****@eos.ncsu.edu> wrote in message
news:bk**********@uni00nw.unity.ncsu.edu...
"JustSomeGuy" <no**@nottelling.com> wrote in message
news:bk***********@nserve1.acs.ucalgary.ca...
I have a need to make an applicaiton that uses a variable number of nested for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


This one was actually a nice little challenge :-)
Here is my implementation (not the fastest one or anything, but seams to
work just fine... under OpenBSD and GCC 2.96 i think).
Hope this helps you. If you need more explanation of how this code works,
let me know, i will be happy to explain.
Notice the stack of for_loop objects is reversed, meaning the top entry
represents the most outer loop, and deeper down the stack => deeper the
nested for loop... recursion rocks!

#include <stack>
#include <string>
#include <iostream>
using namespace std;

class for_loop {
public:
for_loop(const string& name = "", int reps = 0)
: _name(name), _reps(reps), _current(0) {}
int at(void) { return _current; }
void tick(void) { ++_current; }
bool done(void) { return _current == _reps; }
string name(void) { return _name; }

private:
string _name;
int _reps;
int _current;
};

void magic(stack<for_loop> loops, stack<for_loop> outer) {
for_loop temp = loops.top();
loops.pop();

if(!loops.empty()) {
for_loop loop = temp;
for_loop backup = temp;

do {
cout
<< loop.name()
<< ", "
<< loop.at()
<< ", "
<< outer.size()
<< endl;

outer.push(loop);
magic(loops, outer);
outer.pop();

loop.tick();
} while(!loop.done());

loops.push(backup);
} else {
for_loop loop = temp;
for_loop backup = temp;

do {
cout
<< loop.name()
<< ", "
<< loop.at()
<< ", "
<< outer.size()
<< endl;
loop.tick();
} while(!loop.done());
}
}

int main(int args, char **argv) {
for_loop loop0(" loopW", 2);
for_loop loop1(" loopX", 4);
for_loop loop2(" loopY", 3);
for_loop loop3("loopZ", 2);

stack<for_loop> loops;
stack<for_loop> outer;

loops.push(loop0);
loops.push(loop1);
loops.push(loop2);
loops.push(loop3);

magic(loops, outer);

return 0;
}

And the output is:

loopZ, 0, 0
loopY, 0, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopY, 1, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopY, 2, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopZ, 1, 0
loopY, 0, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopY, 1, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3
loopY, 2, 1
loopX, 0, 2
loopW, 0, 3
loopW, 1, 3
loopX, 1, 2
loopW, 0, 3
loopW, 1, 3
loopX, 2, 2
loopW, 0, 3
loopW, 1, 3
loopX, 3, 2
loopW, 0, 3
loopW, 1, 3

Jul 19 '05 #9

P: n/a
"JustSomeGuy" <no**@nottelling.com> wrote in message news:<bk***********@nserve1.acs.ucalgary.ca>...
I have a need to make an applicaiton that uses a variable number of nested
for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


I can't give you an answer because with the information that you've provided
I can't have one.
In order to solve your problem first answer the questions:
+ How do you determine the number of loops,
how is this number passed to the function that does the looping?
+ How are you going to use the loop control variables?

good luck, Stephan
Jul 19 '05 #10

P: n/a

"Stephan Brönnimann" <br****@hotmail.com> wrote in message
news:d1**************************@posting.google.c om...
"JustSomeGuy" <no**@nottelling.com> wrote in message news:<bk***********@nserve1.acs.ucalgary.ca>...
I have a need to make an applicaiton that uses a variable number of nested for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


I can't give you an answer because with the information that you've

provided I can't have one.
In order to solve your problem first answer the questions:
+ How do you determine the number of loops,
how is this number passed to the function that does the looping?
Does not matter man.
Given enough abstraction the function doing the actuall looping need to know
nothing about how many loops it handles (>= 1).
+ How are you going to use the loop control variables?
Also does not matter, a base class for loop can have an interface that can
be implemented in derived types, this way any loop can be customized.

good luck, Stephan


Look at the posts i made to this question, maybe it will clarify things for
ya.

Martin
Jul 19 '05 #11

P: n/a
JustSomeGuy wrote:
I have a need to make an applicaiton that uses a variable number of nested
for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?

How about creating an n dimensional iterator.

Below is somthing I just wrote it's far from a complete system but it
gives you an idea of what you can do. (no range checks etc etc). I'm
not even sure I would model it this way, it's the first thing that came
to mind.

There are all kinds of optimizations you can make if the sizes of the
dimensions are constant.

The code below is very generic and hence not optimal. If your app is a
heavy numerical application, you'll need some hooks to do things more
optimally.
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

//
// nDimensional describes the sizes for each dimension
//
class nDimensional
{
public:
// this contains the dimensions
const int * m_dim_siz;
int m_dim_n;

// constructor
nDimensional( const int * dim_siz, int dim_n )
: m_dim_siz( dim_siz ),
m_dim_n( dim_n )
{
}

// number of elements in a system
int NumEntries()
{
if ( m_dim_n == 0 )
{
return 1;
}

int val = * m_dim_siz;
int count = m_dim_n - 1;
for (
const int * ptr = m_dim_siz + 1;
count > 0;
count --, ptr ++
) {
val *= * ptr;
}

return val;
}
};

//
// nDimensionalIterator allows you to iterate over
// all dimensions
//
class nDimensionalIterator
: public std::vector<int>,
public nDimensional
{
public:
bool m_finished;

nDimensionalIterator( const std::vector<int> & sizes )
: nDimensional( & sizes[0], sizes.size() ),
std::vector<int>( sizes.size(), 0 ),
m_finished( false )
{
}

nDimensionalIterator( const int * sizes, int dimensions )
: nDimensional( sizes, dimensions ),
std::vector<int>( dimensions, 0 ),
m_finished( false )
{
}

nDimensionalIterator( const nDimensional & dims )
: nDimensional( dims ),
std::vector<int>( dims.m_dim_n, 0 ),
m_finished( false )
{
}

//
// post increment iterator
//
inline nDimensionalIterator & operator ++()
{
std::vector<int>::iterator val_iter = begin();
std::vector<int>::iterator val_iter_end = end();
const int * size_iter = m_dim_siz;

while ( val_iter != val_iter_end )
{
int value = ++( * val_iter );

if ( value < * size_iter )
{
m_finished = false;
return * this;
}

* val_iter = 0;

size_iter ++;
val_iter ++;
}

m_finished = true;

return * this;
}

//
// a linear index
//
int Index() const
{
if ( m_dim_n == 0 )
{
return 0;
}

std::vector<int>::const_iterator val_iter = begin();

int index = * ( val_iter ++ );
int val = * m_dim_siz;

int count = m_dim_n - 1;
for (
const int * ptr = m_dim_siz + 1;
count > 0;
count --, ptr ++, val_iter ++
) {
index += ( * val_iter ) * val;
val *= * ptr;
}

return index;
}
};

//
// This defines an n dimensional matrix.
//
template <typename T>
class nDimensionalMatrix
: public std::vector<T>,
public nDimensional
{
public:

nDimensionalMatrix( const int * sizes, int dimensions )
: nDimensional( sizes, dimensions ),
std::vector<T>(
nDimensional( sizes, dimensions ).NumEntries(),
T()
)
{
}

T & operator []( const nDimensionalIterator & iter )
{
return (* static_cast< std::vector<T> *>(this))[ iter.Index() ];
}

};
//
// a 4 dimensional system 4x3x2x4
//
int dim_siz[] = { 4, 3, 2, 4 };
//
// some example code
//
void foo()
{

// create a 4x3x2x4 (4 dimensional) float matrix
//
nDimensionalMatrix< float > f( dim_siz, sizeof( dim_siz )/
sizeof(* dim_siz ) );

float val = 0;

// initialize the matrix
for (
nDimensionalIterator iter( dim_siz, sizeof( dim_siz )/
sizeof(* dim_siz ) );
! iter.m_finished;
++ iter
) {

f[ iter ] = val;

val += 1.1f;

std::copy(iter.begin(), iter.end(),
std::ostream_iterator<int>(std::cout, " "));

std::cout << " index = " << iter.Index();

std::cout << " set to " << f[ iter ];

std::cout << "\n";

}

for (
nDimensionalIterator iter( f );
! iter.m_finished;
++ iter
) {

std::copy(iter.begin(), iter.end(),
std::ostream_iterator<int>(std::cout, " "));

std::cout << " index = " << iter.Index();

std::cout << " f[ iter ] is " << f[ iter ];

std::cout << "\n";

}

}

// test
int main()
{
foo();
}

Jul 19 '05 #12

P: n/a
Hello,

"JustSomeGuy" <no**@nottelling.com> wrote in message news:<bk***********@nserve1.acs.ucalgary.ca>...
I have a need to make an applicaiton that uses a variable number of nested
for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


I would make a counter class. Perhaps you could let it be initialized
by a vector of integers containing the values X,Y,Z. Your for-loop
would be something like.

vector<int>v;
v.push_back(Z);
v.push_back(Y);
v.push_back(X);
for(counters i(v);!i.atend();++i)

You could do the push_back in a loop to allow for a variable number of
loop variables. The atend() method and the operator++, and also the
constructor of this class you will have to write yourself, but they
are not very difficult.

Good luck,
Chris Dams
Jul 19 '05 #13

P: n/a
Marcin Vorbrodt wrote:
New and improved version 2. Much shorter and easier to read:-) Hope this
helps.


Please don't post attachments to non-binary groups. This causes a number
of problems. Place text in the body of your message. If you really need
an attachment, post it to a binary group, and optionally post a
reference in the non-binary group so people know where to go to get it.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

Jul 19 '05 #14

P: n/a
"JustSomeGuy" <no**@nottelling.com> wrote in message news:<bk***********@nserve1.acs.ucalgary.ca>...
I have a need to make an applicaiton that uses a variable number of nested
for loops.

for now I'm using a fixed number:

for (z=0; z < Z; ++z)
for (y=0; y < Y; ++y)
for (x=0; x < X; ++x)
The thing is there could be less or more nested loops necessary.
How can I write this such that the number of for loops is a variable?


I would try something like the following code:

void loopf(std::vector<int> & index, const int max, const int ind);
void loop(const int dim)
{
std::vector<int> index(dim);
loopf(index, dim, 0);
}

void loopf(std::vector<int> & index, const int max, const int ind)
{
if (ind == max)
{ //here you perform the computation you need
//I only print the values of the indices
for (int i = 0; i < index.size(); ++i)
std::cout << index[i] << "|";
std::cout << std::endl;
}
else
{ //here you put the loop you need
for (int j = 0; j < max; ++j)
{
index[ind] = j; // dimension ind recieves value j
loopf(index, max, ind + 1);
}
}
}

It is similar to the code of other post by Philip, but I keep the
value of the indices in the vector for computation.

Regards,

Marcelo Pinto
Jul 19 '05 #15

P: n/a
Thank you all for the answers...
I think (in my opinion.) that the answer lies in recursion....

Many thanks for the hard work you all put into this.

B.
Jul 19 '05 #16

This discussion thread is closed

Replies have been disabled for this discussion.