Ruby: Merging nested array between each other depe

问题:

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]]

回答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.

回答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

回答3:

Here's a very simple approach. The steps are as follows.

1. Beginning with an array a = arr.map(&:uniq), arr being the initial array of arrays, look for two arrays of a that share an element, among all combinations of two arrays of a. If none are found, return a (fini!); else go to step 2.

2. If a[i] and a[j] are found to contain a common element, a[i] becomes a[i].concat(a[j]).uniq and a[j] is deleted.

3. Repeat #1.

def group_unique(arr)
  a = arr.map(&:uniq)
  loop do
    (_,i),(_,j) = a.each_with_index.to_a.combination(2).find {|(a,_),(b,_)|(a&b).any?}
    return a if i.nil?
    a[i] = a[i].concat(a.delete_at(j)).uniq
  end
end

arr = [[1,2], [5,6], [2,3], [4,5], [4,1], [7,8], [11,13], [8,10]]
group_unique(arr)
  #=> [[1, 2, 3, 4, 5, 6], [7, 8, 10], [11, 13]] 

回答4:

It's a little verbose, but here is a recursive method that solves the problem properly:

def merge_shared_elements(list) 
  changed = false 
  result = list.each_with_object([]) do |item, new_list| 
    if existing_item = new_list.find {|new_item| !(new_item & item).empty?} 
      existing_item.concat(item).uniq! 
      changed = true 
    else 
      new_list << item 
    end 
  end 

  changed ? merge_shared_elements(result) : result 
end

This will keep re-iterating through the list, so the order of inputs is irrelevant.