Ruby：根据条件合并彼此之间的嵌套数组

Question

合并嵌套在至少共享一个元素的数组中的数组的最佳方法是什么？这是一个例子：

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

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

或者，更具表现力：

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

最精确的解决方案，适用于任何排列，但会消耗更多时间：

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

Answer 2

有点冗长，但这里有一个递归方法可以正确解决问题：

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

这将不断重复列表，因此输入的顺序无关紧要。

Answer 3

这可行：

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

示例：

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

我正在使用散列 h 来存储与给定元素相对应的数组。散列 returns [] 如果键不存在。

插入 [1, 2] 后，散列如下所示：

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

插入 [2, 3] 时，2 和 3 的数组通过以下方式获取：

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

然后[2, 3]自身被添加：

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

一切都是 |-ed:

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

此结果存储在tmp中。它成为包含键的新值：

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

相当于：

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

之后，h 看起来像这样：

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

最后，通过 h.values | h.values.

返回不同的值

Answer 4

这是一个非常简单的方法。步骤如下

以一个数组a = arr.map(&:uniq)开始，arr为数组的初始数组，在所有组合中寻找共享一个元素的两个a数组a 的两个数组。如果找到 none，则 return a（fini！）；否则转到第 2 步。
如果发现a[i]和a[j]包含共同元素，则a[i]变为a[i].concat(a[j]).uniq并删除a[j]。
重复 #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]]

Ruby：根据条件合并彼此之间的嵌套数组

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

ruby

array-merge