Ruby: Merging nested array between each other depending on a condition

Question

What would be the best way to merge arrays nested in an array that shares at least an element ? Here's an example:

some_method([[1, 2], [2, 3], [4, 5]])
#=> [[1, 2, 3], [4, 5]]
some_method([[1, 2], [2, 3], [3, 4], [5,6]])
#=> [[1, 2, 3, 4], [5, 6]]

Answer 1

This would work:

def some_method(arrays)
  h = Hash.new { |h, k| h[k] = [] }
  arrays.each do |array|
    tmp = h.values_at(*array).push(array).inject(:|)
    tmp.each { |k| h[k] = tmp }
  end
  h.values | h.values
end

Examples:

some_method([[1, 2], [2, 3], [4, 5]])          #=> [[1, 2, 3], [4, 5]]    
some_method([[1, 2], [2, 3], [3, 4], [5, 6]])  #=> [[1, 2, 3, 4], [5, 6]]    
some_method([[1, 3], [3, 4], [2, 5], [4, 5]])  #=> [[1, 3, 4, 2, 5]]

I'm using a hash h to store the array that correspond to a given element. The hash returns [] if a key doesn't exist.

After inserting [1, 2], the hash looks like this:

{
  1 => [1, 2],
  2 => [1, 2]
}

When inserting [2, 3], the arrays for 2 and 3 are fetched via:

h.values_at(2, 3)
#=> [[1, 2], []]

then [2, 3] itself is added:

h.values_at(2, 3).push([2, 3])
#=> [[1, 2], [], [2, 3]]

and everything is |-ed:

h.values_at(2, 3).push([2, 3]).inject(:|)
#=> [1, 2, 3]

This result is stored in tmp. It becomes the new value for the contained keys:

tmp.each { |k| h[k] = tmp }

Which is equivalent to:

h[1] = tmp
h[2] = tmp
h[3] = tmp

Afterwards, h looks like this:

{
  1 => [1, 2, 3],
  2 => [1, 2, 3],
  3 => [1, 2, 3]
}

At the end, the distinct values are returned via h.values | h.values.

Answer 2

arr = [[1, 2], [2, 3], [3, 4], [5, 6]]

arr.map(&:dup).sort.each_with_object([]) do |a, memo|
  (idx = memo.index { |m| !(m & a).empty? }) ? memo[idx] |= a : memo << a
end
#⇒ [[1, 2, 3, 4], [5, 6]]

or, more expressive:

arr.map(&:dup).sort.each_with_object([]) do |a, memo|
  (memo.detect { |m| !(m & a).empty? } << a).
    flatten!.uniq! rescue memo << a
end

the most precise solution, that works for any permutations, but consumes more time:

loop.inject(arr.map(&:dup)) do |acc|
  result = (acc.each_with_object([]) do |a, memo|
    (idx = memo.index { |m| !(m & a).empty? }) ? memo[idx] |= a : memo << a 
  end)
  result == acc ? (break result) : result
end