CODEWITHSUNDEEP
c#algorithm
scubasteve
scubasteve

Reputation: 2858

Need help with algorithm to resolve index through jagged array

Argh! I know I will get this eventually but at this point I'm almost 2 hours into it and still stuck.

I need to resolve the individual indexes for each "level" of a jagged array for a specific location. It's hard to explain, but if you imagine a 3 level jagged array with [2,3,4] lengths. If you then were to flatten that out into a single array it would have a size of 24. Now, let's say you needed to find the the indexes (one for each level of the jagged array) that would be equal to the single array index 22. It would be 1,2,1. It's not hard to figure out a single scenario, but I'm trying to figure out what the algorithm is to resolve these values for a variable depth jagged array.

Here is a simple code sample of my current attempt:

using System;

class Program
{
    static void Main(string[] args)
    {
        //  Build up the data and info about level depth
        int[] levelDepth = new[] { 2, 3, 4 };
        int[][][] data = new int[][][]
        {
            new int[][] { new int[4], new int[4], new int[4] },
            new int[][] { new int[4], new int[4], new int[4] }
        };

        int requestedValue = 22;
        float temp = requestedValue;

        //  Store the index of each level array to get to the index 
        //  for the requested value
        int[] levelIndexes = new int[3] { 0, 0, 0 };

        //  The following does not work!
        int i = levelDepth.Length;
        while (i > 0)
        {
            temp = temp / levelDepth[i - 1];
            levelIndexes[i - 1] = (int)Math.Round(temp);

            i--;
        }
    }
}

It doesn't work correctly, although it ALMOST gets me what I need but I think that just may be luck. I suspect this is a common problem that has been solved before, I just don't have the experience to figure it out. :(

Also, before anyone tells me that using arrays like this is terrible or "why don't you store your data like this" - The above description and code is simulating the layout of some decoder chips on our hardware and I need to work out a way to resolve a path to a specific graph of cascading chips; the above example exactly matches the layout of the chips. I'm stuck with it.

Upvotes: 5

Views: 293

Answers (3)

user684934
user684934

Reputation:

Array of length 2 holds array of length 3, which holds array of length 4.

Thus, the index on the first array will increment your total index by 3*4=12.

Index on second array will increment your total by 4.

Index on third array will increment your total by 1.

So, 22 = 12*1 + 4*2 + 1*1.

After figuring out these numbers (multiply values in levelDepth together), you can simply use a greedy algorithm starting with the outermost array.

int temp = requestedValue;
int levelWeight[] = {levelDepth[2]*levelDepth[1], levelDepth[2], 1};
for(int i=0;i<3;i++){
    while(requestedValue >= levelWeight[i]){
        levelIndexes[i]++;
        requestedValue-=levelWeight[i];
    }
}

Upvotes: 1

Henk Holterman
Henk Holterman

Reputation: 273179

You shouldn't use floats here. 

int[] levelDepth = new[] { 2, 3, 4 };
int requestedValue = 22;
int[] levelIndexes = new int[levelDepth.Length];


for (int i = 0; i < levelDepth.Length; i++)
{
  // need to go from { 2, 3, 4 } -> { 3*4, 4, 1 }
  int f = 1;
  for (int j = i+1; j < levelDepth.Length; j++)      
     f *= levelDepth[j];

  levelIndexes[i] = requestedValue / f;  // integer divide
  requestedValue = requestedValue % f;
}

Upvotes: 3

drharris
drharris

Reputation: 11214

Assuming you need the element's value at that point (and not the specific indices), you can simply perform a ruby-like flatten, and then access the index directly.

Edit: Sorry for the misunderstanding, maybe this will help. From Microsoft Visual C#.NET 2003 Developers Cookbook (Mark Schmidt):

static int[] GetDimensionIndices(int flatIndex, Array array)
{
    int[] indices = new int[array.Rank];
    int p = 1;
    for(int i = array.Rank - 1; i >= 0; i--)
    {
        indices[i] = (((flatIndex/p)) % (array.GetUpperBound(i)+1));

        if(i > 0)
            p *= array.GetUpperBound(i) + 1;
    }
    return indices;
}

Upvotes: 1

Related Questions