JS how to reform this irregular object

I have this object whose keys are guaranteed to be sorted and will be used for the operation. And each of its values ​​is an array of 2d.

var obj = { "0": [ [0, 1], [0, 3], [0, 4] ], "1": [ [1, 2], [1, 3] ], "2": [ [2, 3], [2, 5] ], "3": [ [3, 4], [3, 6] ], "5": [ [5, 6] ], "6": [ [6, 5] ] } 

I am trying to concatenate them, and for each of its last value, the array is the next index of the object. So my expected result is such an array,

Sample - I need to find the path from 0 , which is the first index of obj , the last index, which is 6 , using the values ​​in each of them and linking its last value to the next object. If that makes sense.

 [0, 1, 2, 3, 4, 5, 6] [0, 1, 2, 3, 6] [0, 1, 2, 5, 6] [0, 1, 3, 4, 5, 6] [0, 1, 3, 4] [0, 1, 3, 6] [0, 3, 4, 5, 6] [0, 3, 6] [0, 4] 

This is my code so far, since I do not know how to proceed further.

 var result = []; for (var key in obj) { var myarr = obj[key]; for (var i = 0; i < myarr.length; i++) { result.push(myarr[i]) } } 

Any idea or feedback is welcome.

Edit

One of the expected results was [0, 1, 2, 3, 4, 5, 6] , here is a step-by-step explanation.

  • The obj key starts at 0 and ends at 6 , I need to form a path from 0 to 6 with arrays in its value.
  • Starting with obj[0] , the first array returns [0, 1] , save it until res . ( res now [0, 1] )
  • The last array value in res is 1 , now find the next value in obj[1]
  • obj[1] has two arrays and ends with 2 or 3 .. Thus, you can add both of them, so it can be [0, 1, 2] or [0, 1, 3] . In this case, get the first one, which is [1, 2] , and add the last value to res . ( res now [0, 1, 2] ).
  • The last array value in res now 2 , now find the next value in obj[2] .
  • obj[2] has two arrays and ends with 3 or 5 .. You can add them with both of them, so it can be [0, 1, 2, 3] or [0, 1, 2, 5] . In this case, get the first one that is [2, 3] , and add the last value to res . ( res now [0, 1, 2, 3] )
  • The last array value in res now 3 , now find the next value in obj[3] .
  • Repeat step 4 or 6. ( res now [0, 1, 2, 3, 4] ).
  • The last value of the array in res now 4 , now find the next value in obj[4] .
  • Repeat step 4 or 6. ( res now [0, 1, 2, 3, 4, 5] ).
  • The last array value in res now 5 , now find the next value in obj[5] .
  • A value of 6 will now be found, which should be the end of the iteration if you look at step 4 . Repeat step 4 or 6. ( res now [0, 1, 2, 3, 4, 5, 6] ).
  • Repeat from step 1 and create another way to do this without duplicates [0, 1, 2, 3, 4, 5 ,6] .
+6
source share
2 answers

This offer is with one additional release mentioned below.

 [ [0, 1, 2, 3, 4, 5, 6], [0, 1, 2, 3, 6], [0, 1, 2, 5, 6], [0, 1, 3, 4, 5, 6], /* extended from below */ [0, 1, 3, 4], /* original result */ [0, 1, 3, 6], [0, 3, 4, 5, 6], /* extended from below */ [0, 3, 4], /* extra line, line should not be in result */ [0, 3, 6], /* but follows the same building rule than above */ [0, 4] ] 

Basically this solution is building a tree with given information about related nodes.

If some nodes are not adjacent, for missing links, backtracking is performed with the above function for checkNodes nodes or using iterPath to move the actual assembled nodes for missing elements.

 function getParts(value, path, nodes) { function checkNodes(a) { if (a[1] === value + 1) { getParts(a[1], path.concat(a[1]), nodes); return true; } } function iterPath(k) { return (object[k] || []).some(function (a) { return path[path.length - 1] + 1 === a[1] || iterPath(a[1]); }); } value = value || 0; path = path || [value]; nodes = nodes || []; if (object[value]) { object[value].forEach(function (a, i, aa) { if (a[1] === lastKey) { parts.push(path.concat(a[1])); return; } getParts(a[1], path.concat(a[1]), nodes.concat(aa.slice(i + 1))); }); return; } if (nodes.some(checkNodes)) { return; } path.slice(1).some(iterPath) && getParts(path[path.length - 1] + 1, path.concat(path[path.length - 1] + 1), nodes); parts.push(path); } var object = { 0: [[0, 1], [0, 3], [0, 4]], 1: [[1, 2], [1, 3]], 2: [[2, 3], [2, 5]], 3: [[3, 4], [3, 6]], 5: [[5, 6]], 6: [[6, 5]] }, lastKey = 6, parts = []; getParts(); parts.forEach(function (a) { console.log(JSON.stringify(a)); }); 
 .as-console-wrapper { max-height: 100% !important; top: 0; } 
+8
source

Well, I sat on this for a while and shared my problems:

The input object can be considered as a tree adjacency list :

 var obj={0:[[0,1],[0,3],[0,4]],1:[[1,2],[1,3]],2:[[2,3],[2,5]],3:[[3,4],[3,6]],5:[[5,6]],6:[[6,5]]}; 

and as a result, the following is required: in fact, this is a list of all the root paths of the tree:

 [0,1,2,3,4] [0,1,2,3,6] [0,1,2,5,6] [0,1,3,4] [0,1,3,6] [0,3,4] [0,3,6] [0,4] 

slightly different from the result set mentioned in the question below:

 [0,1,2,3,4,5,6] [0,1,2,3,6] [0,1,2,5,6] [0,1,3,4,5,6] [0,1,3,4] [0,1,3,6] [0,3,4,5,6] [0,3,6] [0,4] 

Difference between the results is only whether 4 and 6 leaf nodes

Decision

Therefore, I assume that for our Tree here:

  • 0 is the root of the node

  • 4 and 6 are leaf nodes

See code below. First I created a tree, and all root paths are listed from it:

 // removed "6:[[6,5]]" as 6 is a 'leaf' of the tree var obj={0:[[0,1],[0,3],[0,4]],1:[[1,2],[1,3]],2:[[2,3],[2,5]],3:[[3,4],[3,6]],5:[[5,6]]}; var availableNodes = Object.keys(obj); var tree = availableNodes.reduce(function(hash) { return function(prev, curr) { hash[curr] = hash[curr] || {}; hash[curr].children = hash[curr].children || []; obj[curr].forEach(function(element) { hash[element[1]] = hash[element[1]] || {}; hash[element[1]].children = hash[element[1]].children || []; hash[curr].rootPath = hash[curr].rootPath || []; hash[curr].children.push({value: element[1],children: hash[element[1]].children}); }); curr && prev.push({value: curr,children: hash[curr].children}); return prev; }; }(Object.create(null)), []); //console.log(JSON.stringify(tree)); var result = []; function rootToLeafPaths(node, path) { path.push(+node.value); if (node.children.length === 0) { result.push(Array.from(path)); path.pop(); } else { node.children.forEach(function(element) { rootToLeafPaths(element, path); }); path.pop(); } } rootToLeafPaths(tree[0], []); console.log(JSON.stringify(result)); 
 .as-console-wrapper{top:0;max-height:100%!important;} 
+2
source

Source: https://habr.com/ru/post/1011760/


All Articles