文章/答案/技术大牛

发布

社区首页 >问答首页 >遍历javascript中的递归关系矩阵

问遍历javascript中的递归关系矩阵
EN

Stack Overflow用户

提问于 2015-11-12 12:51:00

回答 4查看 140关注 0票数 3

有许多元素(表示为复选框)有一些不同的关系。例如：

A需要B
A需要C
A不能与D结合
B不能与E结合
D需要E
C需要F
F不能与G结合
S不能与B结合
T不能与D结合
U需要S

编辑:我想在这里定义的答案中出现了3问题：

问:默认的、禁止的或需要的是什么？他们一个也没有。如果两个元素之间没有关系，它们就可以独立行动(只要与一个共同的元素没有关系，就可以说不是)。
问:如果A禁止B，B会自动禁止A吗？答:是的。猫(A)说，你不能和狗在一起。即使狗不关心猫，你也不能把它们结合在一起，因为猫不会喜欢它。
问:如果A需要B，那么B会自动需要A吗？答:没有。如果要读取堆栈溢出(A)，则需要浏览器(B)。但是，如果要使用浏览器(B)，则不需要堆栈溢出(A)。

编辑：，我想举一个更简单的例子。比方说，您可以配置带有复选框的汽车。有一些规则。例如，如果您选择黑色油漆，您不能选择白色的内部颜色(禁止)。如果你选择皮革座椅，你只能结合座椅加热(需要)和皮革方向盘(需要)，但不能结合电动座椅调节(禁止)。座椅加热是不可能的白色内部(禁止)，而白色的屋顶需要白色的内部。因此，即使没有定义，你也不能有带座椅加热的白色屋顶(由于与普通元素的关系而被禁止)。

因此，如果有人激活复选框A，复选框B和C也需要激活，而复选框D则需要禁用。由于A需要B和B不能与E结合，所以复选框E也需要禁用。因为C需要F，F需要激活。因为F不能和G结合，所以G也需要去激活。

反过来，如果有人激活了E，那么B就需要去激活，因为B不能和E结合，但是D不需要激活，因为D需要E，而E不需要D。

现在的主要问题是：

如何理想地用javascript来表达关系
如果有人激活了复选框，如何检查与javascript的所有关系。

问题是递归。每一次行动都会导致更多的行动，甚至可能导致更多的行动。

下面的逻辑适用于"A“被激活的示例：

B将被激活
C将被激活
D将被禁用
E将被禁用
S将被禁用
T将被禁用
你将被残废

目前对这些关系的定义(可以改变)：

var relations = {
  'A': {
    'B': 'needed',
    'C': 'needed',
    'D': 'prohibited'
  },
  'B': {
    'E': 'prohibited'
  },
  'D': {
    'E': 'needed'
  },
  'C': {
    'F': 'needed'
  },
  'F': {
    'G': 'prohibited'
  },
  'S': {
    'B': 'prohibited'
  },
  'T': {
    'D': 'prohibited'
  },
  'U': {
    'S': 'needed'
  }
}

目前的理论方法：

假设点击"A"：

foreach (relations['A'] as related, relation) {
  if (relation === 'needed') {
    // take action
    activateRelated(related);
  } else if (relation === 'prohibited') {
    // take action
    disableRelated(related);
  }
}

但这只是第一次迭代。从理论上讲，这可能是一个函数，它在每次执行操作后都会递归地调用自己。但是，假设300个元素有很多关系，它的循环是无限的。嗯，如果采取了一项行动，激活了一个复选框，它就能正常工作。在一个更现实的场景中，有30 %到50 %的复选框处于活动状态，对关系的检查需要在整个过程中上下进行。

第二个问题是:如果用户再次禁用复选框A，则需要再次检查所有关系--对于所有仍然处于活动状态的复选框也是如此。

matrix

checkbox

javascript

recursion

回答 4

Stack Overflow用户

回答已采纳

发布于 2015-11-12 14:59:07

也许这个有帮助。If与表单下面的提示一起工作。

编辑:现在用简单的检查循环参考。选定的相互影响的项目首先被取消选举。

编辑2:现在禁用/启用复选框。

var relation = [
        { name: 'A', needed: ['B', 'C'], prohibited: ['D'] },
        { name: 'B', needed: [], prohibited: ['E'] },
        { name: 'C', needed: ['F'], prohibited: [] },
        { name: 'D', needed: ['E'], prohibited: [] },
        { name: 'E', needed: [], prohibited: [] },
        { name: 'F', needed: [], prohibited: ['G'] },
        { name: 'G', needed: [], prohibited: [] },
        { name: 'S', needed: [], prohibited: ['B'] },
        { name: 'T', needed: [], prohibited: ['D'] },
        { name: 'U', needed: ['S'], prohibited: [] }
    ];

void function () {
    var div = document.createElement('div'),
        form = document.createElement('form'),
        loop;
    div.id = 'out';
    form.name = 'boxes';
    relation.forEach(function (a) {            
        var br = document.createElement('br'),
            input = document.createElement('input'),
            label = document.createElement('label');                
        input.type = 'checkbox';
        input.name = a.name;
        input.addEventListener('change', check);
        label.textContent = a.name;
        label.for = a.name;
        label.appendChild(input);
        label.appendChild(document.createTextNode((a.needed.length ? ' needed: ' + a.needed.join(', ') : '') + (a.prohibited.length ? ' prohibited: ' + a.prohibited.join(', ') : '')));
        form.appendChild(label);
        form.appendChild(br);
    });
    form.appendChild(div);
    document.body.appendChild(form);

    do {
        loop = false;
        relation.forEach(function (a) {
            a.needed.forEach(function (aa) {
                relation.forEach(function (b) {
                    b.prohibited.forEach(function (bb) {
                        if (aa === bb) {
                            if (!~a.prohibited.indexOf(b.name)) {
                                a.prohibited.push(b.name);
                                loop = true;
                            }
                            if (!~b.prohibited.indexOf(a.name)) {
                                b.prohibited.push(a.name);
                                loop = true;
                            }
                        }
                    });
                });
            });
        });
    } while (loop);
}();

function check() {
    function getBox(l) { return document.boxes[l].checked; }
    function setBox(l, v) { return document.boxes[l].checked = v; }
    function setBoxDisabled(l, v) { return document.boxes[l].disabled = v; }

    var disabled, msg, loop;

    do {
        disabled = [];
        msg = [];
        loop = false;
        relation.forEach(function (a) {
            if (getBox(a.name)) {
                a.needed.forEach(function (b) {
                    if (!getBox(b)) {
                        msg.push('With ' + a.name + ', ' + b + ' is required');
                        setBox(b, true);
                        loop = true;
                    }
                });
                a.prohibited.forEach(function (b) {
                    if (getBox(b)) {
                        msg.push('With ' + a.name + ', ' + b + ' is prohibited');
                        setBox(b, false);
                        loop = true;
                    }
                    setBoxDisabled(b, true);
                    !~disabled.indexOf(b) && disabled.push(b);
                });
            }
        });
        relation.forEach(function (a) {
            if (!getBox(a.name)) {
                a.prohibited.forEach(function (b) {
                    !~disabled.indexOf(b) && setBoxDisabled(b, false);
                });
            }
        });
        msg.length && out(msg.join('<br>') + '<hr>');
    } while (loop);
}

function out(s) {
    var node = document.createElement('div');
    node.innerHTML = s + '<br>';
    document.getElementById('out').appendChild(node);
}

额外好处:一种略有不同的方法，具有递归风格和适当的更改消息。

var relation = [
        { name: 'A', needed: ['B', 'C'], prohibited: ['D'] },
        { name: 'B', needed: [], prohibited: ['E'] },
        { name: 'C', needed: ['F'], prohibited: [] },
        { name: 'D', needed: ['E'], prohibited: [] },
        { name: 'E', needed: [], prohibited: [] },
        { name: 'F', needed: [], prohibited: ['G'] },
        { name: 'G', needed: [], prohibited: [] },
        { name: 'S', needed: [], prohibited: ['B'] },
        { name: 'T', needed: [], prohibited: ['D'] },
        { name: 'U', needed: ['S'], prohibited: [] }
    ], object = {};

void function () {
    var div = document.createElement('div'),
        form = document.createElement('form');
    div.id = 'out';
    form.name = 'boxes';

    relation.forEach(function (a) {
        var br = document.createElement('br'),
            input = document.createElement('input'),
            label = document.createElement('label');

        input.type = 'checkbox';
        input.name = a.name;
        input.addEventListener('change', function (l) { return function () { checkBox(l); } }(a.name));
        //input.addEventListener('change', function () { checkBox(a.name); });
        label.textContent = a.name;
        label.for = a.name;
        label.appendChild(input);
        label.appendChild(document.createTextNode((a.needed.length ? ' needed: ' + a.needed.join(', ') : '') + (a.prohibited.length ? ' prohibited: ' + a.prohibited.join(', ') : '')));
        form.appendChild(label);
        form.appendChild(br);
        object[a.name] = a;
    });
    form.appendChild(div);
    document.body.appendChild(form);
}();

function checkBox(l) {
    function getBox(l) { return document.boxes[l].checked; }
    function setBox(l, v, x) {
        if (document.boxes[l].checked !== v) {
            v ? out('With ' + x + ' option ' + l + ' is necessary.') : out('Without ' + x + ' option ' + l + ' is not valid.');
            document.boxes[l].checked = v;
        }
    }
    function setBoxDisabled(l, v, x) {
        if (document.boxes[l].disabled !== v) {
            v ? out('With ' + x + ' option ' + l + ' is not available.') : out('Without ' + x + ' option ' + l + ' is now available.');
            document.boxes[l].disabled = v;
        }
    }

    if (getBox(l)) {
        object[l].prohibited.forEach(function (p) {
            setBox(p, false, l);
            setBoxDisabled(p, true, l);
            relation.forEach(function (a) {
                if (~a.needed.indexOf(p)) {
                    setBox(a.name, false, p);
                    setBoxDisabled(a.name, true, p);
                    checkBox(a.name);
                }
            });
            checkBox(p);
        });
        object[l].needed.forEach(function (p) {
            setBox(p, true, l);
            checkBox(p);
        });
    } else {
        var allProhibited = [];
        relation.forEach(function (a) {
            if (getBox(a.name)) {
                a.prohibited.forEach(function (b) {
                    !~allProhibited.indexOf(b) && allProhibited.push(b);
                });
            }
        });
        object[l].prohibited.forEach(function (p) {
            if (!~allProhibited.indexOf(p)) {
                setBox(p, false, l);
                setBoxDisabled(p, false, l);
            }
            relation.forEach(function (a) {
                if (~a.needed.indexOf(p)) {
                    setBox(a.name, false, p);
                    setBoxDisabled(a.name, false, p);
                    checkBox(a.name);
                }
            });
            checkBox(p);
        });
        relation.forEach(function (a) {
            if (~a.needed.indexOf(l)) {
                setBox(a.name, false, l);
                checkBox(a.name);
            }
        });
    }
}

function out(s) {
    var node = document.createElement('div');
    node.innerHTML = s + '<br>';
    document.getElementById('out').appendChild(node);
}

票数 1

Stack Overflow用户

发布于 2015-11-12 13:22:53

编辑:对需求进行了改进

简单的递归是做不到的

var relations = {
  'A': {
    'B': 'needed',
    'C': 'needed',
    'D': 'prohibited'
  },
  'B': {
    'E': 'prohibited'
  },
  'D': {
    'E': 'needed'
  },
  'E':{/* added for simplicity */},
  'C': {
    'F': 'needed'
  },
  'F': {
    'G': 'prohibited'
  }
};
var tmp = {};
function checkRelations(start) {
  for (var relation in relations[start]) {
    if (!tmp.hasOwnProperty(relation)) {
       tmp[relation] = {};
    }
    if (relations[start][relation] === 'needed') {
      tmp[relation][start] = 'needed';
    } else if (relations[start][relation] === 'prohibited') {
      tmp[relation][start] = 'prohibited';
    }
    checkRelations(relation);
  }
}
function run(obj) {
  for (var e in obj) {
    checkRelations(e);
  }
}

run(relations);
JSON.stringify(tmp);

你会得到这样的结果：

{
  'B': {
    'A': 'needed',
    'S': 'prohibited'
  },
  'E': {
    'B': 'prohibited',
    'D': 'needed'
  },
  'C': {
    'A': 'needed'
  },
  'F': {
    'C': 'needed'
  },
  'G': {
    'F': 'prohibited'
  },
  'D': {
    'A': 'prohibited',
    'T': 'prohibited'
  },
  'S': {
    'U': 'needed'
  }
}

正如您从第一个条目B中看到的那样:您的数据库是定义不足的。没有定义的每个元素都会发生什么？什么是默认的，如果某物没有定义，它是prohibited还是‘需要’？如果'A'需要'B'，这意味着'B'需要'A'

一旦定义了您可以填充数据库的第一层(自动)并在此基础上构建一棵树(dito自动)，如果您需要并安全地处理大量的处理(O(n^2))，则可以花费大量的内存(O(n^2))。

所有的假设，整个事情是一致的，没有无限循环任何地方！

将默认值设置为'meh'后，第一轮是

function checkRelations(start) {
  for (var relation in relations[start]) {
    if (!relations.hasOwnProperty(relation)) {
      relations[relation] = {
      };
    }
    if (relations[start][relation] === 'needed') {
      relations[relation][start] = 'meh';
    } else if (relations[start][relation] === 'prohibited') {
      relations[relation][start] = 'prohibited';
    }
    for (var r in relations) {
      if (!relations[relation].hasOwnProperty(r) && relation != r) {
        relations[relation][r] = 'meh';
      }
    }
  }
}
function run(obj) {
  for (var e in obj) {
    // fill database up
    checkRelations(e);
  }
}
run(relations);
JSON.stringify(relations)
{
  'A': {
    'B': 'needed',
    'C': 'needed',
    'D': 'prohibited',
    'E': 'meh',
    'F': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'B': {
    'E': 'prohibited',
    'A': 'meh',
    'D': 'meh',
    'C': 'meh',
    'F': 'meh',
    'S': 'prohibited',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'E': {
    'B': 'prohibited',
    'A': 'meh',
    'D': 'meh',
    'C': 'meh',
    'F': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'D': {
    'E': 'needed',
    'A': 'prohibited',
    'B': 'meh',
    'C': 'meh',
    'F': 'meh',
    'S': 'meh',
    'T': 'prohibited',
    'U': 'meh',
    'G': 'meh'
  },
  'C': {
    'F': 'needed',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'D': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'F': {
    'G': 'prohibited',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'D': 'meh',
    'C': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh'
  },
  'S': {
    'B': 'prohibited',
    'A': 'meh',
    'E': 'meh',
    'D': 'meh',
    'C': 'meh',
    'F': 'meh',
    'T': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'T': {
    'D': 'prohibited',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'C': 'meh',
    'F': 'meh',
    'S': 'meh',
    'U': 'meh',
    'G': 'meh'
  },
  'U': {
    'S': 'needed',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'D': 'meh',
    'C': 'meh',
    'F': 'meh',
    'T': 'meh',
    'G': 'meh'
  },
  'G': {
    'F': 'prohibited',
    'A': 'meh',
    'B': 'meh',
    'E': 'meh',
    'D': 'meh',
    'C': 'meh',
    'S': 'meh',
    'T': 'meh',
    'U': 'meh'
  }
}

已经很贵了。你可以扩展这棵树，但是我会在这里停下来，沿着路径'needed'在飞行中构建树。您应该能够使用第一个递归方法来完成它，如果您找到一个“needed”(如果默认值是'prohibited' )，则可以使用recurse。

示例：

A - B(n) - C(n) - D(p)        
    |       |
    E(p)   F(n)
    ||      |
    S(p)   G(p)

(一条是一根树枝，两根是一片叶子)

当然，根据默认值处理'meh'部件。如果默认情况是'meh'，则甚至可以完全跳过'prohibited'条目的构造，只剩下'needed'条目。

剩下的会是

{
  'A': {
    'B': 'needed',
    'C': 'needed'
  },
  'B': {
    'nothing':0
  },
  'E': {
    'nothing':0
  },
  'D': {
    'E': 'needed'
  },
  'C': {
    'F': 'needed'
  },
  'F': {
    'nothing':0
  },
  'S': {
    'nothing':0
  },
  'T': {
    'nothing':0
  },
  'U': {
    'S': 'needed'
  },
  'G': {
    'nothing':0
  }
}

并降至最低限度：

{
  'A': {
    'B': 'needed',
    'C': 'needed'
  }
  'D': {
    'E': 'needed'
  },
  'C': {
    'F': 'needed'
  }
  'U': {
    'S': 'needed'
  }
}

完整算法:如果需要，将所有条目设置为'prohibited'，并遍历上面列出的由以下小脚本创建的小DB

function checkRelations(start) {
  for (var relation in relations[start]) {
    if (relations[start][relation] === 'prohibited') {
      delete relations[start][relation];
    }
  }
}
function isEmpty(obj) {
  for(var p in obj) {
    if(obj.hasOwnProperty(p)){
      return false;
    }
  }
  return true;
}
function run(obj) {
  for (var e in obj) {
    // fill database up
    checkRelations(e);
    // delete empty entries
    if(isEmpty(relations[e])){
      delete relations[e];
    }
  }
}

遍历最后一条的函数：

function followPath(start){
  for (var relation in reduced[start]) {
    console.log(relation + " is needed")
    if (reduced.hasOwnProperty(relation)) {
      console.log( relation + " is needed, follow path")
      followPath(relation);
    }
  }

}

啊，迟到了。再一次;-)

但至少它比我一开始想象的要简单一些(如果我正确计算循环的话，速度更快)。

票数 1

Stack Overflow用户

发布于 2015-11-12 13:53:44

您给出的作为示例的关系类型可以表示为具有标记边的有向图：

在上面的图像中，边缘的颜色表示边缘的标签或标签：

绿色:需求

红色:禁止

边缘上的点代表关系的方向。

现在您已经知道可以使用图论算法遍历/搜索数据了。请参见：

深度优先搜索

广度优先搜索

在javascript中，我会像这样存储数据：

var graph = { v: [], e: [] } // v: vertices or nodes, e: edges

这取决于你将如何一个顶点或节点的样子。它可以是字符串，也可以是html复选框元素，甚至可以是包含两者的对象：

var vertex = { 
  name: "A",
  el : someElement
};

有向图中的边如下所示：

var edge = {
  s: sourceVertex,
  d: destinationVertex,
  tag: "n"   // the tag will define the type of relation
  // again you can use strings: 'n' - `needs` and 'p' - `prohibits`
  // or whatever type you like       
};

SO33673055我还不确定这是不是你需要的。从用户更改的复选框开始，只检查一次所有规则。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/33671842

复制

相似问题

问遍历javascript中的递归关系矩阵
EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问遍历javascript中的递归关系矩阵EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问遍历javascript中的递归关系矩阵
EN