Search

Categories

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Send mail to the author(s) E-mail

# Monday, 29 September 2014

Had to go from xUnit to NUnit to get debug information in real time in debug: http://stackoverflow.com/questions/15092438/using-resharper-how-to-show-debug-output-during-a-long-running-unit-test

http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-10-recursion/#_Toc362296468

code in https://github.com/djhmateer/StudentProjects  (currently in recd branch)

N nested loops
Each loop goes from 1 to K

If N=2 and K=3 output is:

image

N=3 and K=2 output is:

image

image
Image from website.  Strategy is to find a recurrent dependence.

public class RecursiveNestedLoops {
    int numberOfNestedLoops; // N - number of nested for sequenceOfValues
    int numberOfIterations; // K - for 1..K
    int[] sequenceOfValues;

    [Test]
    public void DoSomething() {
        numberOfNestedLoops = 3;
        numberOfIterations = 2;
        sequenceOfValues = new int[numberOfNestedLoops];
        NestedLoops(0);
    }

    public void NestedLoops(int currentLoop) {
        // Got to the bottom of the recursion, print and return
        if (currentLoop == numberOfNestedLoops) {
            PrintLoops();
            return;
        }

        // Setup an iteration from 1..K in this nestedloop
        for (int counter = 1; counter <= numberOfIterations; counter++) {
            sequenceOfValues[currentLoop] = counter;
            NestedLoops(currentLoop + 1);
        }
    }

    public void PrintLoops() {
        var message = "";
        for (int i = 0; i < numberOfNestedLoops; i++) {
            message += String.Format("{0} ", sequenceOfValues[i]);
        }
        Debug.WriteLine(message);
    }
}

Iterative Version

It is possible to do the same without recursion.  Lets see if it is easier to understand:

Output is the same for  numberOfNestedLoops N=3, numberOfIterations:  K=2
image

  • Start with a sequenceOfValues array of 1 1 1
  • Print current sequenceOfValues
  • Increment with 1 the number at position N.  If > K replace with 1and increment with 1 the value at position N-1.  If its value has become greater than K, replace it with 1 etc..
  • sequenceOfValues
    • 1 1 2
    • 1 1 3 (invalid so go inside while)
    • 1 2 1
    • 1 2 2
    • 1 2 3 (invalid so go inside while)
    • 1 2 1 (still inside while)
    • 1 3 1 (still inside while, and invalid)
    • 1 1 1 (still inside while)
    • 2 1 1
    • 2 1 2
    • 2 1 3 (invalid so go inside while)
    • 2 1 1 (inside while)
    • 2 2 1
    • 2 2 2
    • 2 2 3 (invalid so go inside while)
    • 2 2 1 (still inside while)
    • 2 3 1 (still inside while and invalid)
    • 2 1 1 (still inside while)
    • 3 1 1 (still inside while and invalid)
    • 1 1 1 (still inside while and return)

The effect is just like nested for loops.

public class NestedLoopsIterative {
    int numberOfNestedLoops;
    int numberOfIterations;
    int[] sequenceOfValues;
    int lastPositionInArray;

    [Test]
    public void DoSomething() {
        numberOfNestedLoops = 3;
        numberOfIterations = 2;
        lastPositionInArray = numberOfNestedLoops - 1;
        sequenceOfValues = new int[numberOfNestedLoops];
        NestedLoops();
    }

    public void NestedLoops() {
        InitLoops();
        while (true) {
            PrintLoops();

            int currentPositionInSOV = lastPositionInArray;
            sequenceOfValues[currentPositionInSOV] += 1;

            while (sequenceOfValues[currentPositionInSOV] > numberOfIterations) {
                sequenceOfValues[currentPositionInSOV] = 1;
                currentPositionInSOV--;

                if (currentPositionInSOV < 0) return; // break out of while
                sequenceOfValues[currentPositionInSOV] += 1;
            }
        }
    }

    public void InitLoops() {
        for (int i = 0; i < numberOfNestedLoops; i++) {
            sequenceOfValues[i] = 1;
        }
    }

    public void PrintLoops() {
        var message = "";
        for (int i = 0; i < numberOfNestedLoops; i++) {
            message += String.Format("{0} ", sequenceOfValues[i]);
        }
        Debug.WriteLine(message);
    }
}

I like this version, as slightly easier to understand.

Apply to StudentProjects

Implemented using TDD.

image
In release mode in a console app, 7 Students, and 10 Projects taking 26secs.  Actually 7 secs with no print statement.

Summary of Brute Force

This has been great fun... but by brute force I've hit the big O problem :-)  The business logic works, and can do N loops (students) and K iterations (projects)

https://github.com/djhmateer/StudentProjects

I got the non recursive version of N Loops from:

http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-10-recursion/#_Toc362296468

which I think is slightly easier to understand than the recursive version.

Found that NUnit is better than xUnit when wanting to debug and show output.

Think I'm ready to throw my code away now!!!  Although I did have an idea about pre generating the sequences...

Where now?

| | #