How to find the path to a node in a tree of arrays, given its flattened array index?

Question

Here is a snippet from this answer to a related question:

const data = [
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
]

function divide(data, size) {
  const result = []

  for (let i = 0; i < data.length; i += size) {
    const chunk = data.slice(i, i + size);
    result.push(chunk)
  }

  if (result.length > size) {
    return divide(result, size)
  }

  return result;
}

const result = divide(data, 5);
console.log(result)

The data array is simply an array of integers. However, when you run it through divide, it produces a tree of nested arrays with a maximum size of each array. How can I say "give me item number 42" in the tree version of the "compiled" array? For example, I want this 2 value right here, which is number 42 (index 41), if this is sorta what the tree looks like:

[                                                                                       ]
 [                   ],[                   ],[                   ],[                   ]
  [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]   [ ],[ ],[ ],[ ],[ ]
   1   6   1   6   1     6   1   6   1   6     1   6   1   6   1     6   1   6   1   6
   2   7   2   7   2     7   2   7  (2)  7     2   7   2   7   2     7   2   7   2   7
   3   8   3   8   3     8   3   8   3   8     3   8   3   8   3     8   3   8   3   8
   4   9   4   9   4     9   4   9   4   9     4   9   4   9   4     9   4   9   4   9
   5   0   5   0   5     0   5   0   5   0     5   0   5   0   5     0   5   0   5   0

The path to it is [0, 1, 3, 1]. How can I quickly and most optimally get this path given the index 41 in the array? What is the general equation given the divide function above and arbitrary chunking of the array into different sized bins?

---

This is as best as I can start so far, based on @Quade's answer:

let i = 42
let s = 5
let d = 3
let x = 0
let v = new Array(d)
while (d) {
  if (i < s ** d) {
    v[x] = 0
  } else {
    v[x] = Math.floor(i / (s ** d))
  }
  d--
  x++
}

Answer 1

Essentially the path is the index expressed in base size, where the latter is the maximum array size of the division. For example, 41 in base 5 is 131. Hence [1, 3, 1]. I think you mistakenly prefixed this with an additional 0 (just try console.log(result[1][3][1]) in your snippet).

Now, for lower indexes, you would need to prepad one or more zeroes so the path length is always the same for a given tree. The number of digits you need depends on the depth of the tree, which is determined by the largest index in the data. In your example, your data has a size of 100, so largest index is 99. 99 in base 5 is still 3 digits. So any path should have 3 digits in this case.

Remark about your implementation

The divide function currently does not produce the correct result when the data size is smaller than the chunk size. In that case it should just return the original array, but your code still wraps it in another array.

The fix is to make the size check at the start:

if (data.length <= size) return data;

Implementation

// Get path. Note that the actual tree is not needed; just the data size and chunk size
function getPath(chunkSize, dataSize, index) {
    if (index >= dataSize) throw new Error("index out of range");
    // Take logarithm, base chunkSize, from the highest possible index (i.e. dataSize - 1)
    let depth = Math.floor(Math.log(dataSize - 1) / Math.log(chunkSize)) + 1;
    let path = [];
    for (let i = 0; i < depth; i++) {
        // get each "digit" of the index when represented in base-chunkSize
        path.push(index % chunkSize);
        index = Math.floor(index / chunkSize);
    }
    return path.reverse();
}

let path = getPath(5, 100, 41);
console.log("path", path);

// Create the tree and extract that number at that index:
const data = [
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
]

// I moved the base case detection first, so it works correctly 
//   for trees that are just the original array.
function divide(data, size) {
    if (data.length <= size) return data;
    const result = [];
    for (let i = 0; i < data.length; i += size) {
        result.push(data.slice(i, i + size))
    }
    return divide(result, size);
}

const tree = divide(data, 5);

// Now get the value using the path we got
let drill = tree;
while (path.length) {
    drill = drill[path.shift()];
}
console.log("value at path", drill);

Answer 2

I will give an algorithm run with the example, and let you write the general form. Let max=5 and element=42nd

It's a recusion, that goes one layer down each recursive step. Each step you are in a high level array that 42 belongs to.

You start by the top layer array. How much elements it can contain 125=5x5x5 (to generalize max^number_of_sub_layers). 42 is smaller than 125 so it is contained in this array. You have the first 0 of the result [0]

Now to know in which sub layer the next step will look in, you compute 42 // 25 (25=5x5 being the number of elements that each sub array can contain). You get 42 // 25 = 1, so 42 is in the second array (of index 1), you have now [0, 1].

Now you do the same thing with this second array. But with the number 42 % 25 = 17, because 25 elements are contained in the first array. You compute 17 // 5 (5 being the number of elements that each sub array contain). You get 17 // 5 = 3, so 42 will be in the forth sub array of this array (of index 3). So now you have [0, 1, 3]

And then once you are at the array of final layer, the element is in 17 % 5 = 2nd position.

Update

As I am not very familiar with javascript, here is how I would do it in python. The code can be more concise but it does the job.

result = []
nblayers = 3 # can be easily computed given your input array data, I let you do it

def compute(array, size, element, depth):
    """
    size plays the role of 5 in the example
    element plays the role of 42
    depth starts with 0 in the top layer array and increments by 1 each level. 
    """
    nbElements = size ** (nblayers - depth) # max Number of elements that the array can contain
    nbChildElements = size ** (nblayers - depth - 1) # max number of elements each sub array can contain
    if element > nbElements: # element index is not in the list 
        return False

    if depth == nblayers - 1: # if we are at the leaf array
        if element < len(array):
            result.append(element)
            return True
        else: 
            return False # this can happen only for the last subarray, because only it can contain fewer elements

    else:
        childArray = element // nbChildElements # child array in which this element will appear
        result.append(childArray)
        return compute(array[childArray], size, (element%nbChildElements), depth+1)



#here is you call the function with your inputs
compute(data, 5, 42, 0)

Update 2 About Python operators and functions:

• ** : is power
• [] : is an empty list
• len(list) : returns the length of the list
• //: integer division. eg: 5 // 3 = 1
• %: is the modulo operation. eg: 5 % 3 = 2
• list.append(element) : add element to the list list
• array[index] : returns the element at index index in array

Answer 3

You coulöd convert the wanted index to a string with a base and pad the string with the max length of the greatest value.

This approahc works for bases until 10.

const
    getPath = (value, max, base) => value
        .toString(base)
        .padStart(max.toString(base).length, 0)
        .split('');

console.log(getPath(41, 99, 5))

For greater bases until 36, you nedd to add a mapping for getting a number.

const
    getPath = (value, max, base) => Array.from(
        value.toString(base).padStart(max.toString(base).length, 0),
        v => parseInt(v, base)
    );

console.log(getPath(255, 255, 16))