Function to group equivalent elements of an array

Question

Is there a javascript or coffeescript function (or maybe an extension of the underscore groupBy function) that receives as parameters an array and an equivalence comparator (a boolean function with TWO arguments, not just ONE argument) and groups the array elements based on this equivalence comparator?

As an example of what I want:

areEquivalent = (p1, p2) ->
  p1.birthYear == p2.birthYear and
  p1.birthPlace == p2.birthPlace and
  p1.gender == p2.gender

p1 = {name:'Anna', birthYear: 1990, birthPlace: 'Alaska', gender: 'female', hasCar: true, hasChildren: false}
p2 = {name:'John', birthYear: 1990, birthPlace: 'Alaska', gender: 'male', hasCar: true, hasChildren: false}
p3 = {name:'Dora', birthYear: 1980, birthPlace: 'Hawaii', gender: 'female', hasCar: true, hasChildren: true}
p4 = {name:'Lumi', birthYear: 1980, birthPlace: 'Hawaii', gender: 'female', hasCar: false, hasChildren: false}
p5 = {name:'Jack', birthYear: 1990, birthPlace: 'Alaska', gender: 'male', hasCar: false, hasChildren: false}

console.log areEquivalent p1, p2
# false
console.log areEquivalent p3, p4
# true

people = [p1, p2, p3, p4, p5]

console.log _.groupEquivalentObjects(people, areEquivalent)
# [ [p1], [p2,p5], [p3,p4] ]

Can you extend the equivalence function to a comparison function and use a sort? (It doesn't matter what order the comparison function produces, as long as it's self-consistent.) — user2357112, Jul 07 '13 at 00:00
Also, you know this'll run in time quadratic in the number of equivalence classes, right? It'd be much faster if you could somehow produce an identity code for each equivalence class and use `groupBy`. — user2357112, Jul 07 '13 at 00:05
What I put in the title were not meant as tags, but they were alternative choices for the implementation :) (meaning that I was searching for an implementation in either/some of coffeescript or javascript or underscore) — Sorin Postelnicu, Jul 07 '13 at 01:08
Not getting this question--underscore's `groupBy` **already** takes a function. "Splits a collection into sets, grouped by the result of running each value through iterator." Did you read its documentation? — , Jul 08 '13 at 17:16
@torazaburo: Yes, I am aware of Underscore's groupBy function. But it takes a function with only ONE argument - the currently iterated item in the collection. What I need is a version with TWO arguments: pairs of the items in the collection. And yes, I am aware that this can be O(NxN), but that's not important in this case. — Sorin Postelnicu, Jul 09 '13 at 15:06
See http://stackoverflow.com/questions/194846/is-there-any-kind-of-hashcode-function-in-javascript. `JSON.stringify` might work. — , Jul 10 '13 at 04:03

score 4 · Answer 1 · answered Jul 07 '13 at 00:41

Can you not just pass _.groupBy() and expression which will differentiate your inputs properly?

p1 = {name:'Anna', birthYear: 1990, birthPlace: 'Alaska', gender: 'female', hasCar: true, hasChildren: false}
p2 = {name:'John', birthYear: 1990, birthPlace: 'Alaska', gender: 'male', hasCar: true, hasChildren: false}
p3 = {name:'Dora', birthYear: 1980, birthPlace: 'Hawaii', gender: 'female', hasCar: true, hasChildren: true}
p4 = {name:'Lumi', birthYear: 1980, birthPlace: 'Hawaii', gender: 'female', hasCar: false, hasChildren: false}
p5 = {name:'Jack', birthYear: 1990, birthPlace: 'Alaska', gender: 'male', hasCar: false, hasChildren: false}

people = [p1, p2, p3, p4, p5]

groups = _.groupBy(people, (x) -> '' + x.birthYear + x.birthPlace + x.gender)

console.log groups

http://jsfiddle.net/vKz6r/

score 0 · Answer 2 · answered Jul 07 '13 at 01:24

Thank you all for your answers and suggestions.

For the moment I implemented this not-very-optimal solution:

# Modifies the received array, by removing all the elements equivalent to the first one,
# and returning them in a separate array
extractAllObjectsEquivalentToFirst = (array, areEquivalent) ->
  return [] if array.length == 0
  first = array.shift()
  equivalent = [first]
  different = []
  while array.length > 0
    elem = array.shift()
    if areEquivalent(elem,first)
      equivalent.push elem
    else
      different.push elem
  array[..] = different
  return equivalent

groupEquivalentObjects = (array, areEquivalent) ->
  arrayClone = array[..]
  groups = []
  previous = arrayClone.length
  while arrayClone.length > 0
    groups.push extractAllObjectsEquivalentToFirst(arrayClone, areEquivalent)
    if arrayClone.length >= previous
      console.warn "Array length did not decrease!"
      arrayClone = []
    previous = arrayClone.length
  return groups

But indeed a better solution would be to define some kind of hashCode() function for the items, and pass that function as a parameter to _.groupBy()

In my current use case, some of the object properties that I need to compare are actually arrays, for which I need to use _.isEqual() inside the equivalence comparator.

And for the moment I'm too lazy to think of a way to define a "hashCode" function that would ensure the unequivocal equivalence of values for my use case.

Function to group equivalent elements of an array

2 Answers2