javascript - 在javascript中遍历递归关系矩阵

Question

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

• A需要B
• A需要C
• A不能和D结合
• B不能和E结合
• D 需要 E
• C需要F
• F不能与G组合
• S不能和B结合
• T不能和D结合
• 你需要S

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

• 问:默认、禁止或需要的是什么？答:都没有。如果 2个元素之间没有关系，它们可以独立行动 (只要与一个共同的元素没有关系就可以说 否则)。

• 问:如果 A 禁止 B，那么 B 是否会自动禁止 A？答:是的。 猫(A)说，你不能和狗(B)一起吃。就算是狗 不关心猫，你不能把它们结合起来，因为猫 不会喜欢的。

• 问:如果 A 需要 B，那么 B 是否自动需要 A？ A: 不，如果你想 要阅读 stackoverflow (A)，您需要浏览器 (B)。但如果你想 要使用浏览器 (B)，您不需要 stackoverflow (A)。

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

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

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

现在的大问题是:

1. 如何在javascript中理想地表达关系
2. 如果有人激活，如何检查与 javascript 的所有关系 一个复选框。

问题是递归。每个 Action 都会导致更多 Action ，而更多 Action 会(可能)导致更多 Action 。

以下逻辑适用于“A”被激活的示例:

1. B将被激活
2. C将被激活
3. D 将被禁用
4. E 将被禁用
5. S 将被禁用
6. T 将被禁用
7. 你将被禁用

关系的当前定义(可以更改):

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，则需要再次检查所有关系 - 对于所有仍处于事件状态的复选框也是如此。

Answer 1

也许这有帮助。如果与表单下方的提示一起使用。

编辑:现在可以简单地检查循环引用。相互影响的选中项首先被取消选中。

编辑 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);
}