2

嗨，我在 json key:value、key:value 等中有一个很长的键值对列表

car <--> wheel
wheel <--> tyre
bed <--> sheets
guitar <--> strings
guitar <--> pickup
tyre <--> rubber

我想要的是将所有关系分组到数组中，无论这样的距离有多远

[car, wheel, tyre, rubber]
[guitar, strings, pickup]
[bed, sheets]

使用 Javascript 执行此操作的有效方法是什么？

4

2 回答 2

1

首先，我会将关系存储为数组，以便您可以拥有重复的“键”。关键方法：包含与每个单词相关的每个单词的初始字典；使用 map 和 reduce 的递归链扩展器；基于等价的过滤链。

Array.prototype.getUnique = function(){
   var u = {}, a = [];
   for(var i = 0, l = this.length; i < l; ++i){
      if(u.hasOwnProperty(this[i])) {
         continue;
      }
      a.push(this[i]);
      u[this[i]] = 1;
   }
   return a;
}
var links = {};
var pairs = [
    ["car", "wheel"],
    ["wheel", "tyre"],
    ["bed", "sheets"],
    ["guitar", "strings"],
    ["guitar", "pickup"],
    ["rubber", "tyre"],
    ["truck", "wheel"],
    ["pickup", "car"]
];
pairs.map(function(pair) {
    links[pair[0]] = links[pair[0]] || [];
    links[pair[1]] = links[pair[1]] || [];

    links[pair[0]].push(pair[1]);
    links[pair[1]].push(pair[0]);
});
var append = function(list) {
    var related = list.map(function(item) {
        return links[item];
    }).reduce(function(listA, listB) {
        return listA.concat(listB);
    }).filter(function(item) {
        // make sure related only includes new links
        return list.indexOf(item) == -1
    }).getUnique();

    return related.length ? append(list.concat(related)) : list.concat(related);
};
var branches = [];
for( var word in links ) {
    branches.push(append(links[word].concat(word)));
}
var compareArrays = function(listA, listB) {
    if( listA.length != listB.length ) return false;
    return listA.map(function(element) {
        if( listB.indexOf(element) == -1 ) return 0;
        return 1;
    }).filter(function(el) {
        return el == 1;
    }).length == listA.length;
};
var _branches = branches;
var chains = branches.filter(function(branch1, i) {     
    var isUnique = _branches.filter(function(branch2) {
        // are they equivalent
        return compareArrays(branch1, branch2);
    }).length == 1; 
    delete _branches[i];
    return isUnique;
});
于 2012-08-20T22:42:23.927 回答
0

我会使用单词映射，将它们当前所在的集合链接起来。映射（一个 JavaScript 对象）具有接近 O(1) 的运行时来访问一个键应该有助于提高性能。从@matt3141 提出的相同格式开始：

var pairs = [
    ["car", "wheel"],
    ["wheel", "tyre"],
    ["bed", "sheets"],
    ["guitar", "strings"],
    ["guitar", "pickup"],
    ["rubber", "tyre"],
    ["truck", "wheel"],
    ["pickup", "car"]
];

var setsByWord = {};
for (var i=0; i<pairs.length; i++) {
    var pair = pairs[i];
    if (pair[0] in setsByWord && pair[1] in setsByWord) {
        // both words are already known
        if (setsByWord[pair[0]] === setsByWord[pair[1]]) {
             ; // We're lucky, they are in the same set
        } else {
             // combine the two sets
             var sets = [setsByWord[pair[0]], setsByWord[pair[1]]];
             var larger = sets[1].length > sets[0].length ? sets[1] : sets[0],
                 smaller = sets[+(larger===sets[0])];
             for (var j=0; j<smaller.length; j++)
                 setsByWord[smaller[j]] = larger;
             Array.prototype.push.apply(larger, smaller);
        }
    } else {
        // add the missing word to the existing set
        // or create a new set
        var set = setsByWord[pair[0]] || setsByWord[pair[1]] || [];
        if (!(pair[0] in setsByWord)) {
            set.push(pair[0]);
            setsByWord[pair[0]] = set;
        }
        if (!(pair[1] in setsByWord)) {
            set.push(pair[1]);
            setsByWord[pair[1]] = set;
        }
    }
}
return setsByWord;

这会将您的图拆分为其连接的组件（在setsByWord对象中，这些组件数组由节点索引）：

> var results = [];
> for (var word in setsByWord)
>     if (results.indexOf(setsByWord[word])<0)
>         results.push(setsByWord[word]);
> return results;

[
    ["car","wheel","tyre","rubber","truck","guitar","strings","pickup"],
    ["bed","sheets"]
]

如果你有一个有向图，并且想要按单词排列所有后继的数组，你可以使用这个：

var pairs = […],
    graph = pairs.reduce(function(map, pair) {
         (map[pair[0]] || (map[pair[0]] = [])).push(pair[1]);
         return map;
    }, {});

var successors = {};
for (var word in graph) (function getSuccessors(word) {
    if (word in successors)
        return successors[word];
    successors[word] = [true]; // some marker against circles
    return successors[word] = word in graph
        ? [].concat.apply(graph[word], graph[word].map(getSuccessors))
        : [];
})(word);
return successors;

如果您确定图中没有圆圈并且只想要路径初学者的列表，您可以添加以下内容：

var results = [];
for (var word in successors)
    for (var i=0; word in successors && i<successors[word].length; i++)
        delete successors[successors[word][i]];
for (var word in successors)
    results.push([word].concat(successors[word]));
return results;

// becomes:
[
   ["bed","sheets"],
   ["guitar","strings","pickup","car","wheel","tyre"],
   ["rubber","tyre"],
   ["truck","wheel","tyre"]
]
于 2012-08-21T03:32:25.623 回答