How to convert the index of a flatten multidimensional array (any depth) to the original index?

displaydisplayname 0
Viewed 75

For example, suppose I have a multidimensional array:

const a1=[["a",["a","b"]],"b",[["b"],"c"]];

which the flatten from is

const a2=["a","a","b","b","c","c"];

and accessing a2[2] is equivalent to a1[0][1][1], also access a2[3] is equivalent to a1[1].

However I'm not interested in what the element is in such index, instead I want a function that can convert the index of a2 equivalent to in a1, eg:

magicFunction(2,[["a",["a","b"]],"b",[["b"],"c"]])

returns [0,1,1],

also

magicFunction(3,[["a",["a","b"]],"b",[["b"],"c"]])

returns [1]. And the input multidimensional array can be any depth (more than 3 layers). How do I write such magic function?

Note: I know that may be easy to do if I know the array is 2d and the sub-array have same number of elements:

const a1=[["a","a"],["b","b"],["c","c"]];
const magicFunction=function(target,a){
  let count=0;
  for(let i=0;i<a.length;i++){
    for(let j=0;j<a[i].length;j++){
        if(count==target){
            return [i,j];
        }
        count++;
    }
  }
  return [];
};
alert(magicFunction(3,a1));

However now I need the function to accept a with n-dimensional array which d is unknown before testing, which I don't know how many layers of for-loop should I write to handle it, also the length of each sub-array may not be the same.

multidimensional-array arrays javascript
3 Answers

Here's a recursive function that generates the path by traversing the array and counting values until it reaches the n'th value. The function returns either an array of the path (if we reach the n'th value) or the current count (if we don't).

const magicFunction = (index, array, count=0) => {
  for (let idx = 0; idx < array.length; idx++) {
    if (Array.isArray(array[idx])) {
      let res = magicFunction(index, array[idx], count)
      if (Array.isArray(res)) return [idx].concat(res)
      else count = res
    }
    else {
      if (count == index) return [idx]
      count++
    }
  }
  return count
}

for (i = 0; i < 6; i++) {
  res = magicFunction(i, [["a",["b","c"]],"d",[["e"],"f"]])
  console.log(`${i} : [${res}]`)
}

usergAKD0

You can flatten an array into a list of [element path] pairs and fetch paths from that list:

function* flatWithPaths(a, parent=[]) {
    for (let [i, e] of a.entries()) {
        if (Array.isArray(e))
            yield* flatWithPaths(e, parent.concat(i))
        else
            yield [e, parent.concat(i)]
    }
}

//

const a = [["a",["b","c"]],"d",[["e","f"],[[["g","h"]]]]]

let n = 0

for (let [elem, path] of flatWithPaths(a)) {
    console.log(n++, elem, path.join())

}

gog0 
const x = ['1', ['2', '3'], '4', ['5', ['6', '7', ['8', '9']], '10'], '11'];
function getter(arr) {
  let array = [];
  for (let i = 0; i < arr.length; i++) {
    if (!Array.isArray(arr[i])) {
      array.push(arr[i]);
    } else {
      array = array.concat(getter(arr[i]))
    }
  }
  return array;
}

console.log(getter(x));

result: [ '1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11' ]

SwaD0
Related