reduce duplicate in a javascript object

Question

I've got an object like:

{
    a : 'foo',
    b : 'bar',
    c : 'foo',
    d : 'baz',
    e : 'bar'
}

I want to reduce the duplicates like:

{
    ac : 'foo',
    be : 'bar',
    d : 'baz'
}

What's a good way to do that?

A few caveats:

• There will only ever be a small number of pairs. (Currently there are 7; I could imagine it going up to, say, 20.)
• The initial property names will only ever be a single character, like in the example
• The values could potentially run to several hundred characters.
• both speed and code-length are highly important, but given the small number of rows, code clarity is probably still most important.

Answer 1

Go through each property of the object and construct another object, where the keys are the values of the first, and the values are lists of keys (from the first). Then you go back through that second object and make the final result.

Something like this:

function noDupes(obj) {
  var o2 = {};
  for (var k in obj) {
    if (obj.hasOwnProperty(k)) {
      var list = o2[obj[k]] || [];
      list.push(k);
      o2[obj[k]] = list;
    }
  }
  var rv = {};
  for (k in o2) {
    if (o2.hasOwnProperty(k))
      rv[o2[k].join('')] = k;
  }
  return rv;
}

Now, if the values of the original object are not strings, then things get more involved: only strings can be property keys in a Javascript object. You could look around for a more general hash implementation, in that case. If your objects tend to be pretty small (fewer than 10 or so properties) you could write up the n² version, where you simply iterate over the properties and then iterate again for each one. That would probably be a bad idea however if your objects might be large and you have to perform this operation a lot.

Answer 2

var Reduce = function(obj)
{
  var temp = {};
  var val = "";

  for (var prop in obj)
  {
    val = obj[prop];
    if (temp[val])
      temp[val] = temp[val] + prop.toString();
    else
      temp[val] = prop.toString();
  }

  var temp2 = {};

  for (var prop in temp)
  {
    val = temp[prop];
    temp2[val] = prop.toString();
  }

  return temp2;
};

Use as:

var obj = {
  a :"foo",
  b : "bar",
  c : "foo",
  d : "bar", 
  e : "bar"
};

var ob2 = Reduce(obj);

Answer 3

This is the shortest I could get it:

var obj, newObj = {}; // obj is your original
for (var i in obj) {
    if (!obj.hasOwnProperty(i)) continue;
    for (var j in newObj) {
        if (newObj.hasOwnProperty(j) && newObj[j] === obj[i]) break;
        j = "";
    }
    newObj[i + j] = obj[i];
    j && delete newObj[j];
}

Explanation:

• It loops through each item in the original object, obj, and produces a new object, newObj.
• For each item in the original, it searches the half-produced newObj for the same value. - The result is j, either the name of the property if found, or an empty string if not.
• In either case, the new object needs a property of the same name as the current property in the original object, plus this value of j.
• It also deletes the found property in newObj if there was one, to prevent duplicates being constructed.

Admittedly, setting j = "" within the loop is inefficient. This can easily be replaced with a second variable set to "" initially, and j only if a match is found. I decided to go for simplicity though.

Answer 4

Without a higher-kind library just loop each pair (use hasOwnProperty) and add/append the key to a histogram where the histogram key is the pair value and the histogram values are the concatenated keys. Then reverse the key/values of the histogram.

Edit: If the initial values are not strings (and don't map reversibly) then an existing 'identity hash' library might still enable the above approach to work.

Alternatively, you can map to say, [[k,v],...] and sort and then use an approach similar to a bucket sort (imagine it's already sorted) to merge values of "equal keys" in the output pass.

It may go like this (while the code may have bugs, the approach is sound -- it will also work with arbitrary objects as values so long as you have a way to compare the values):

var _f = []
for (var k in map) {
  if (map.hasOwnProperty(k)) {
    _f.push({k: k, v: map[k]})
  }
}
// you could also sort on name (a.k), if it's important
// this makes it more versatile and deterministic in output
// ordering than the histogram method above
var f = _f.sort(function (a, b) { return a.v < b.v ? 1 : a.v > b.v ? -1 : 0 })

var res = {}
var prev
var name = ""
// after the sort all {k:,v:} objects with the same values will be grouped
// together so we only need to detect the change to the next value
// and everything prior to that gets the merged key
for (var i = 0; i < f.length; i++) {
  var p = f[i]
  if (prev != p.v && name) {
    res[name] = prev
    name = ""
  } else {
    name = name + p.k
  }
  prev = p.v
}
if (name) { // don't forget last set of values
  res[name] = prev
}

// have res

Answer 5

Forgive me if I'm completely out, but it seems to me that the way you're combining these, you've got the keys and the values the wrong way around. What about this?

{
    'foo': ['a', 'c'],
    'bar': ['b', 'e'],
    'baz': ['d']
}

Should be easy enough to convert:

flippedObj = {};
for (var letter in obj) {
    if (obj.hasOwnProperty(letter)) {
        var letters = flippedObj[obj[letter]];
        if (letters === undefined) {
            letters = [];
            flippedObj[obj[letter]] = letters;
        }

        letters.push(letter);
    }
}

(Brain-compiled; there might be a couple of errors.)

Answer 6

Start with a reduce that uses a dictionary to count the tags in a flipped way. Very performant way since it uses the built in dictionary support, no for loops etc.

var flipped = Object.keys(input).reduce(function(a,b){
  var tag = input[b];
  a[tag] = (a[tag] || '') + b;
  return a;
}, {});

Returns an object with flipped format:

// {foo: "ac", bar: "be", baz: "d"}

Then just flip the format:

Object.keys(flipped).reduce(function(a,b){
  a[flipped[b]]=b;
  return a;
}, {});

Output:

// {ac: "foo", be: "bar", d: "baz"}