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 に答える