0

I have a 2-D array (with dimensions magnitudes n by 5), which I'm picturing in my head like this (each box is an element of the array):

(http://tr1.cbsistatic.com/hub/i/2015/05/07/b1ff8c33-f492-11e4-940f-14feb5cc3d2a/12039.jpg)

In this image, n is 3. I.e, n is the number of columns, 5 is the number of rows in my array.

I want to find an efficient way to iterate (i.e walk) through every path that leads from any cell in the left most column, to any cell in right most column, choosing one cell from every column in between.

It cannot be simply solved by n nested loops, because n is only determined at run time.

I think this means recursion is likely the best way forward, but can't picture how to begin theoretically.

Can you offer some advice as to how to cycle through every path. It seems simple enough and I can't tell what I'm doing wrong. Even just a theoretical explanation without any code will be very much appreciated.

I'm coding in C#, Visual Studio in case that helps.

UPDATE:: resolved using code below from http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-10-recursion/#_Toc362296468

static void NestedLoops(int currentLoop)
{
if (currentLoop == numberOfLoops)
{
    return;
}

for (int counter=1; counter<=numberOfIterations; counter++)
{
    loops[currentLoop] = counter;
    NestedLoops(currentLoop + 1);
}
}
gurudewan
  • 1
  • 2
  • 1
    Please provide an attempt at solving this problem for yourself. – Nate Mar 23 '16 at 20:29
  • *"I want to find an efficient way to iterate (i.e walk) through every path that leads from any cell in the left most column, to any cell in right most column, choosing one cell from every column in between."* you need to define the rules a lot better than that. If I'm in cell `m,n` which cells am I allowed to move into in column `n+1`? – Matt Burland Mar 23 '16 at 20:55
  • 1. you start at the left-most column, y0 with any x coordinate 2. if you're in a cell (x, y), you can only move to a cell with x-coordinate (x+1), but with any y coordinate 3. you must end at the right most column, yn, with any x coordinate – gurudewan Mar 23 '16 at 20:59
  • the solution must iterate through every route that is possible above systematically – gurudewan Mar 23 '16 at 21:02

2 Answers2

0

This is a factorial problem and so you might run quite quickly into memory or value limits issues.

Took some code from this SO post by Diego.

class Program
{
    static void Main(string[] args)
    {
        int n = 5;
        int r = 5;
        var combinations = Math.Pow(r, n);
        var list = new List<string>();
        for (Int64 i = 1; i < combinations; i++)
        {
            var s = LongToBase(i);
            var fill = n - s.Length;
            list.Add(new String('0', fill) + s);
        }

        // list contains all your paths now

        Console.ReadKey();
    }

    private static readonly char[] BaseChars = "01234".ToCharArray();
    public static string LongToBase(long value)
    {
        long targetBase = BaseChars.Length;
        char[] buffer = new char[Math.Max((int)Math.Ceiling(Math.Log(value + 1, targetBase)), 1)];
        var i = (long)buffer.Length;
        do
        {
            buffer[--i] = BaseChars[value % targetBase];
            value = value / targetBase;
        }
        while (value > 0);
        return new string(buffer);
    }
}

list will contain a list of numbers expressed in base 5 which can be used to found out the path. for example "00123" means first cell, then first cell then second cell, then third cell and finall fourth cell.

Jonathan Nappee
  • 430
  • 2
  • 11
0

Resolved:: see the code posted in the edited question above, and the link to a recursion tutorial, where it takes you through using recursion to simulate N nested, iterative loops.

gurudewan
  • 1
  • 2