如何使用 javascript 找到对称和自反

Question

对于我的作业，我必须找出关系集（我从二维数组中获取）是否对称 or/and transitive.Below 是关系的二维数组，R= {(1,3),(2,2),(2,3),(3,2),(3,1)} //当我从用户输入中获取值时，这种关系可能会改变。

var r = new Array(5);
r[0] = [1,3];
r[1] = [2,2];
r[2] = [2,3];
r[3] = [3,2];
r[4] = [3,1];

所以我想知道的是如何根据这个数组来识别。我已经为对称做了，但它仍然没有显示正确的结果。基于数组，它应该得到输出 "IT IS SYMMETRIC"。我仍然找不到对称的，所以我无法继续寻找它是否具有传递性。

for(var i = 0; i < 5; i++){ //row
    for(var j = 1; j < 5; j++){ 
        if(r[i][1] == r[j][0])  
        {
            if(r[i][0] == r[j][1])
            {
                symmetric = symmetric + 1;
            }
        }
        else if (r[i][0] == r[i][1])
            {
                symmetric = symmetric + 1;
            }
        else 
        {
            symmetric = -1;
        }
    }
    //j= j + 1;
}
if(symmetric > 0)
{
    alert("IT IS SYMMETRIC");
}
else
    alert("IT IS NOT SYMMETRIC");

Answer 1

您可以采用 Set 并删除对称对或自反对。最后检查集合的大小，如果为零，则所有项目都已分配，对称或自反。

var r = [[1, 3], [2, 2], [2, 3], [3, 2], [3, 1]],
    pairs = new Set(r.map(a => a.toString()));
    
r.forEach(([x, y]) => {
    if (x === y) {
        pairs.delete([x, y].toString());
        return;
    }
    pairs.delete([x, y].toString()) && pairs.delete([x, y].toString());
});

console.log(!pairs.size);

Answer 2

在输入数组上使用两个循环执行此操作效率不高。最好先将关系的定义转换为嵌套的对象值结构，这样您就可以在常数时间内检索某个对是否在关系中。

对于对象可能如下所示的示例数据：

{
    "1": {
        "3": true
    },
    "2": {
        "2": true,
        "3": true
    },
    "3": {
        "1": true,
        "2": true
    }
}

以下是如何在线性时间内创建该对象以及如何在线性时间内确定对称性：

var r = [[1,3], [2,2], [2,3], [3,2], [3,1]];

function isSymmetric(r) {
    // convert to object
    var rel = {}
    for (var i = 0; i < r.length; i++) {
        if (!(r[i][0] in rel)) rel[r[i][0]] = {};
        rel[r[i][0]][r[i][1]] = true;
    }
    // Test to see if opposite relation is in object
    for (var a in rel) {
        for (var b in rel[a]) {
            if (!rel[b] || !rel[b][a]) return false;
        }
    }

    return true;
}

console.log(isSymmetric(r));

传递性

传递性需要考虑第三个值。当以下两个关系成立时：a→b 和b→c 那么a→c 也必须成立。这需要根据与上述代码相同的模式进行额外循环：

var r = [[1,3], [2,2], [2,3], [3,2], [3,1]];

function isTransitive(r) {
    // convert to object
    var rel = {}
    for (var i = 0; i < r.length; i++) {
        if (!(r[i][0] in rel)) rel[r[i][0]] = {};
        rel[r[i][0]][r[i][1]] = true;
    }
    // Test to see if opposite relation is in object
    for (var a in rel) {
        for (var b in rel[a]) {
            if (!rel[b]) continue;
            for (var c in rel[b]) {
                if (!rel[a][c]) return false;
            }
        }
    }
    return true;
}

console.log(isTransitive(r));

ES6 版本

当然，这可以使用 Map、Set 和其他一些好东西用 ES6 更简洁地编写：

const r = [[1,3], [2,2], [2,3], [3,2], [3,1]];

function isSymmetric(r) {
    // convert to Map
    var rel = new Map(r.map(pair => [pair[0], new Set]));
    r.forEach(([a, b]) => rel.get(a).add(b));
    // Test to see if opposite relation is in Map
    return r.every(([a, b]) => rel.has(b) && rel.get(b).has(a));
}

console.log(isSymmetric(r));

传递性 (ES6)

代码与上面最后一个代码块（ES6）相同，最后一行更改为：

return r.every(([a, b]) => !rel.has(b) || [...rel.get(b)].every(c => rel.get(a).has(c)));

如何使用 javascript 找到对称和自反

How to find Symmetric and reflexive using javascript

javascript

discrete-mathematics

传递性

ES6 版本

传递性 (ES6)