Filter unique pairs from JSON using Javascript

Question

I have an array of objects each of which has a left and right element. In some cases the within the array, the left may equal the right and visa versa for distinct objects within the array. These "duplicates" need to be removed.

So for example, I have an array of objects like this...

[
    {"left":"cow","right":"pig"},
    {"left":"horse","right":"pig"},
    {"left":"rabbit","right":"pig"},
    {"left":"bird","right":"pig"},
    {"left":"bear","right":"pig"},
    {"left":"cow","right":"bird"},
    {"left":"horse","right":"bird"},
    {"left":"pig","right":"bird"},
    {"left":"cow","right":"horse"},
    {"left":"bird","right":"horse"},
    {"left":"pig","right":"horse"},
    {"left":"rabbit","right":"horse"},
    {"left":"horse","right":"cow"},
    {"left":"pig","right":"cow"},
    {"left":"bird","right":"cow"},
    {"left":"bear","right":"cow"},
    {"left":"horse","right":"rabbit"},
    {"left":"pig","right":"rabbit"},
    {"left":"bear","right":"rabbit"},
    {"left":"pig","right":"bear"},
    {"left":"rabbit","right":"bear"},
    {"left":"cow","right":"bear"}
]

And I need to filter it down to the unique pairs, like this...

[
    {"left":"cow","right":"pig"},
    {"left":"horse","right":"pig"},
    {"left":"rabbit","right":"pig"},
    {"left":"bird","right":"pig"},
    {"left":"bear","right":"pig"},
    {"left":"cow","right":"bird"},
    {"left":"horse","right":"bird"},
    {"left":"cow","right":"horse"},
    {"left":"rabbit","right":"horse"},
    {"left":"bear","right":"cow"},
    {"left":"bear","right":"rabbit"}
]

Using javascript.

You accidentally included `{"left":"pig","right":"bird"},` in your expected output. It is a duplicate. See my response below. — Mr. Polywhirl, Oct 19 '15 at 23:00

score 4 · Answer 1 · answered Oct 19 '15 at 22:34

You're going to need to use Array.prototype.filter, as well as a basic object to keep track of which pairs have been touched.

var input = [ ... ];
var pairs = {};
var output = input
    .filter(function(item) {
        if (pairs[item.left] == item.right ||
            pairs[item.right] == item.left)
            return false;
        pairs[item.left] = item.right;
        return true;
    });

score 0 · Answer 2 · edited May 23 '17 at 12:00

Well, the easiest way to keep track of items is to create a map. We will treat this like it were a set. We will simply sort the left and right items, hash them, and then store the computed hash into the map by assigning the key a value of true. When we arrive at the same hash later on, we will know that we have already marked the pair. The duplicates will be filtered out.

I borrowed the hashing logic below from user LordVlad. You may provide your own method of hashing.

document.body.innerHTML = printItems(pruneItems(getItems()));

function pruneItems(items) {
  var hashes = {};

  return items.filter(function(item, idx, arr) {
    var hash = hashStr([item.left, item.right].sort().join(''));

    if (hashes[hash] !== true) {
      return (hashes[hash] = true);
    }

    return false
  }, []);
}

function hashStr(str) {
  return str.split('').reduce(function(res, ch) {
    res = ((res << 5) - res) + ch.charCodeAt(0);
    return res & res
  }, 0);
}

function printItems(items) {
  return '[\n' + items.map(function(item) {
    return '\t' + JSON.stringify(item).replace(/([,])/g, '$1 ');
  }).join('\n') + '\n]\n';
}

function getItems() {
  return [
    { "left": "cow",    "right": "pig"    },
    { "left": "horse",  "right": "pig"    },
    { "left": "rabbit", "right": "pig"    },
    { "left": "bird",   "right": "pig"    },
    { "left": "bear",   "right": "pig"    },
    { "left": "cow",    "right": "bird"   },
    { "left": "horse",  "right": "bird"   },
    { "left": "pig",    "right": "bird"   },
    { "left": "cow",    "right": "horse"  },
    { "left": "bird",   "right": "horse"  },
    { "left": "pig",    "right": "horse"  },
    { "left": "rabbit", "right": "horse"  },
    { "left": "horse",  "right": "cow"    },
    { "left": "pig",    "right": "cow"    },
    { "left": "bird",   "right": "cow"    },
    { "left": "bear",   "right": "cow"    },
    { "left": "horse",  "right": "rabbit" },
    { "left": "pig",    "right": "rabbit" },
    { "left": "bear",   "right": "rabbit" },
    { "left": "pig",    "right": "bear"   },
    { "left": "rabbit", "right": "bear"   },
    { "left": "cow",    "right": "bear"   }
  ];
}

body {
  font-family: monospace;
  white-space: pre;
}

Result

[
    {"left":"cow", "right":"pig"}
    {"left":"horse", "right":"pig"}
    {"left":"rabbit", "right":"pig"}
    {"left":"bird", "right":"pig"}
    {"left":"bear", "right":"pig"}
    {"left":"cow", "right":"bird"}
    {"left":"horse", "right":"bird"}
    {"left":"cow", "right":"horse"}
    {"left":"rabbit", "right":"horse"}
    {"left":"bear", "right":"cow"}
    {"left":"bear", "right":"rabbit"}
]

guest271314 · Answer 3 · 2015-10-20T01:20:29.253

Try using Array.prototype.forEach() , Array.prototype.some() , RegExp.prototype.test()

var res = [];
arr.forEach(function(val, key) {  
    var re = new RegExp(val.left + "|" + val.right);
    if (!res.some(function(v, k) {
      return re.test(v.left) && re.test(v.right)
    })) {
      res.push(val)
    }
});

var arr = [{
  "left": "cow",
  "right": "pig"
}, {
  "left": "horse",
  "right": "pig"
}, {
  "left": "rabbit",
  "right": "pig"
}, {
  "left": "bird",
  "right": "pig"
}, {
  "left": "bear",
  "right": "pig"
}, {
  "left": "cow",
  "right": "bird"
}, {
  "left": "horse",
  "right": "bird"
}, {
  "left": "pig",
  "right": "bird"
}, {
  "left": "cow",
  "right": "horse"
}, {
  "left": "bird",
  "right": "horse"
}, {
  "left": "pig",
  "right": "horse"
}, {
  "left": "rabbit",
  "right": "horse"
}, {
  "left": "horse",
  "right": "cow"
}, {
  "left": "pig",
  "right": "cow"
}, {
  "left": "bird",
  "right": "cow"
}, {
  "left": "bear",
  "right": "cow"
}, {
  "left": "horse",
  "right": "rabbit"
}, {
  "left": "pig",
  "right": "rabbit"
}, {
  "left": "bear",
  "right": "rabbit"
}, {
  "left": "pig",
  "right": "bear"
}, {
  "left": "rabbit",
  "right": "bear"
}, {
  "left": "cow",
  "right": "bear"
}];

var res = [];
arr.forEach(function(val, key) {  
    var re = new RegExp(val.left + "|" + val.right);
    if (!res.some(function(v, k) {
      return re.test(v.left) && re.test(v.right)
    })) {
      res.push(val)
    }
});

console.log(arr, JSON.stringify(arr, null, 2)
            , res, JSON.stringify(res, null, 2));

document.querySelector("pre").textContent = JSON.stringify(res, null, 2)

<pre></pre>

Filter unique pairs from JSON using Javascript

3 Answers3

Result