C#: N For Loops

Question

How would I convert this code to have n nested for loops:

            int num = 4;

            for (int i = 0; i <= num; i++)
            {
                for (int j = 0; j + i <= num; j++)
                {
                    for (int k = 0; i + j + k <= num; k++)
                    {
                        for (int l = 0; i + j + k + l <= num; l++)
                        {
                            Console.WriteLine(i + " " + j + " " + k + " " + l);
                        }
                    }
                }
            }

So if num is 2 then there would only be 2 for loops; i and j.

This is NOT homework and I was hoping to do it iteratively. Each Console.WriteLine() needs to be stored as like an element all together.

The output of this programs creates n dimensional hyperspase exponents.

Answer 1

OK, you want a nonrecursive solution which is parameterized in num and has a constant number of nested loops, yes?

Here's a sketch of a method that does that. Filling out the details is left as an exercise.

First, I assume that you have an immutable type "Vector" which can be a 0-tuple, 1-tuple, 2-tuple, 3-tuple, ... n-tuple.

The method takes in the size of the vector and returns a sequence of vectors of that size.

IEnumerable<Vector> MakeVectors(int num)
{
    Vector current = new Vector(num); // make an all-zero vector with num items.
    while(true)
    {
        yield return current;
        Vector next;
        bool gotAnother = GetNextVector(current, out next);
        if (!gotAnother) break;
        current = next;
    }
}

There. The problem has now been reduced to two smaller problems:

1) Given a vector of size num, is it the last vector in the sequence?

2) If not, what is the next vector?

It should be quite straightforward to work out what the next vector is given the current one: increase the value of the last slot. If that makes it too big, set it to zero and increase the value of the previous slot. Repeat until you've found the thing that is to be increased.

Make sense?

Answer 2

Normally, you'd use recursion for scenarios where you have nested loops where the number of nested loops is unknown at compile time. Something with the idea of:

void func(const vector<int> &times, int depth) {
    if (depth == times.size()) return;
    for (int i = 0; i < times[depth]; ++i) {
        cout << depth;
        func(times, depth + 1);
    }
}

Answer 3

Taking you on your word that this is not homework, see below:

    public void LoopRecursively(Stack<int> valuesSoFar, int dimensions)
    {
        for (var i = 0; SumOf(valuesSoFar) + i <= dimensions; i++)
        {
            valuesSoFar.Push(i);
            if (valuesSoFar.Count == dimensions)
            {
                Console.WriteLine(StringOf(valuesSoFar));
            }
            else
            {
                LoopRecursively(valuesSoFar, dimensions);
            }
            valuesSoFar.Pop();
        }
    }

    private int SumOf(IEnumerable<int> values)
    {
        return values.Sum(x => x);
    }

    private string StringOf(IEnumerable<int> values)
    {
        return string.Join(" ", values.Reverse().Select(x => x.ToString()).ToArray());
    }

Answer 4

As an alternative to manipulating the digits separately, as is done in the recursive solutions and the ones that use a Vector<>, you can rely on machine representations and arithmetic. This is no faster if you need to examine each digit each time through the loop, but if you're implementing an iterator then it will reduce your storage space within the iterator, and if you're not using every single value then it may also improve your efficiency. In any case, it's an interesting equivalent approach. Here goes...

First think about the slightly more general case where you have n nested loops, each of which counts from 0 to num. In that case, you are essentially just counting from 0 to num^n - 1 in base num. So you can do something like this:

for( int x=0; x<(num^n); x++ )
{
   int digit_0 = x % num;
   int digit_1 = (x/num) % num;
   int digit_2 = (x/num^2) % num;
   // etc.
}

Note that:

• If no native integer type is large enough for your application, then you will have to use some kind of large integer class. This will reduce the efficiency of the storage and increment parts, though maybe not as much as using a vector of length num.
• If you really do look at each digit each time, then you need a vector of digits, and you have not gained anything. This is really most useful when you're not looking at all the digits each time.
• All the divisors should be precomputed, so you do need to keep around a vector for that!

Anyway, for your particular question, you didn't want to count to num each time, you wanted to count to num - (the sum of the already decided digits). The simplest way to account for this simply by putting an appropriate continue condition into your loops. Here is is with some values substituted in for when n=2 and num=10:

for( x=0; x<100; x++ ) // i.e. x < num*num
{
   int ones = x%10; // i.e. x % num
   int tens = (x/10) % 10; // i.e. (x/num) % num

   if( ones + tens < 10 )
   {
     // actually do work
   }
}

(In case it's not obvious, I don't mean you should actually use 100 and 10 in the code, this is just an illustrative example.)

You can make this more efficient by computing how much to increment x by, or by reducing the range of x and then mapping directly to your subspace instead of to the entire space. (But in 2-d and 3-d you are using exactly half the possible values, so that extra work would only get you a speedup of 2. I think it's the same when n>3, but I am too lazy to figure it out right now, sorry!)