通过 JavaScript 对象递归

Question

正在尝试清理递归管道中的灰尘。谁能帮帮我？

我有一个 JavaScript 键对象，它的值中包含其他键的数组。使用 JavaScript 我正在尝试规范化列表，以便我可以看到哪些键属于相关键的依赖项。让我直观地解释一下：

这是对象 (itemDepsMap):

{
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
}

所以关键four取决于three，这取决于one和two，这取决于 one 和 zero

我需要一个名为 checkDeps(id) 的函数，它将 return 如下所示

checkDeps('four') => [三、二、一、零] checkDeps('two') => [一，零]

我相信这叫做闭包。我也相信这是递归完成的。

这是我的：

  this.checkDeps = function(id) {
    var closure = [];
    if(this.itemDepsMap[id] !== ''){
      for(var dep in this.itemDepsMap[id]) {
        console.log(this.itemDepsMap[id][dep]);
        closure = this.checkDeps(this.itemDepsMap[id][dep]);
      }
    }
    return closure;
  }

非常感谢您的帮助！重复项并不重要，但如果解决方案不添加重复项（优雅地..），则会加分

Answer 1

我提出了一个很简单的方法。您可以将其作为参考。它将 return 一个独特的数组

var itemDepsMap =
{
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
};

function makeUnique(value, index, self) { 
    return self.indexOf(value) === index;
}

var closure = [];
var checkDeps = function(id) {
    if(itemDepsMap[id] !== ''){
      for(var dep in itemDepsMap[id]) {
        console.log(itemDepsMap[id][dep]);
        closure.push(itemDepsMap[id][dep]);
        checkDeps(itemDepsMap[id][dep]);
      }
    }
    closure = closure.filter( makeUnique );
};

checkDeps('four');
console.log(closure);

Answer 2

只是简单的递归，只使用一个完全独立的函数：

var omap = {
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
};

function tracer(key, logger) {
  obj = omap[key] ? omap[key] : obj[key];
  if (!obj || obj == 'undefined') { return logger; }
  obj.forEach(function(elem) { 
    if (logger.indexOf(elem) < 0) { 
      tracer(elem, logger); logger.unshift(elem);         
    }
  });
  return logger;
}

snippet.log('four - ' + tracer('four', [])); 
snippet.log('three - ' + tracer('three', [])); 
snippet.log('two - ' + tracer('two', []));

<script src="//tjcrowder.github.io/simple-snippets-console/snippet.js"></script>

只需使用键和一个空数组调用 tracer。

例如tracer('four', []) 到运行键 four 上的痕迹。

Answer 3

你可以使用两个函数这里是我的代码

var itemDepsMap = {
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
}

var closure = [];

function checkDeps(id){

    var dep = itemDepsMap[id];

    if(dep == '') return;

    for(var i = 0; i < dep.length; i++){

        if(closure.indexOf(dep[i]) == -1){
            closure.push(dep[i]);
            checkDeps(dep[i]);
        }       
    }
}


function test(){

    checkDeps('two');
    console.log(closure);

}

用于测试的功能测试

Answer 4

另一种不需要要求的方式：

function f(id, obj) {
  if (obj[id] == '') return [];//if not dependencies return at once

  var path = obj[id],//save dependecies to check
    p = {},//result dependencies
    cur;//pointer to current 
  while (path.length) {
    do {
      cur = path.shift();//get first dependency that not checked
    } while (cur && p[cur]);

    if (!cur) break;//if nothing current break loop

    p[cur] = true; //mark dependency as checked
    if (obj[cur] != '') {//if current field have dependency
      path = path.concat(obj[cur]);//add to saved dependecies
    }
  }

  return Object.keys(p);
}

function f(id, obj) {
  if (obj[id] == '') return [];

  var path = obj[id],
    p = {},
    cur;
  while (path.length) {
    do {
      cur = path.shift();
    } while (cur && p[cur]);

    if (!cur) break;
    p[cur] = true;
    if (obj[cur] != '') {
      path = path.concat(obj[cur]);
    }
  }

  return Object.keys(p);
}

t={
  "zero" : '',
  "one"  : ['zero'],
  "two"  : ['one'],
  "three": ['one', 'two'],
  "four" : ['three']
};

document.getElementById('r').innerHTML = JSON.stringify(t)
+ '<br /><br />' + JSON.stringify(f('four',t))
+ '<br />' + JSON.stringify(f('two',t));

<div id="r"></div>

通过 JavaScript 对象递归

Recursion through JavaScript Object

javascript

recursion

graph-traversal