在Ruby中合并数组项

编辑: 马丁·德米洛密码被修正了。

运行Martin Demello代码(接受的答案)时,我得到:

[["B", "C", "E", "F"], ["A", "B", "C", "D"], ["F", "G"]] =>
[["B", "C", "E", "F", "A", "D", "G"], ["A", "B", "C", "D"], ["F", "G"]]
and
[["B", "C", "E", "F"], ["A", "B", "C", "D"], ["G"], ["G", "H"]] =>
[["B", "C", "E", "F", "A", "D"], ["A", "B", "C", "D"], ["G", "H"], ["G", "H"]]

这似乎不符合你的规格。

以下是我使用他的一些想法的方法:

a = [["B", "C", "E", "F"], ["A", "B", "C", "D"], ["F", "G"]]
b = [["B", "C", "E", "F"], ["A", "B", "C", "D"], ["G"], ["G", "H"]]

def reduce(array)
  h = Hash.new {|h,k| h[k] = []}
  array.each_with_index do |x, i| 
    x.each do |j|
      h[j] << i
      if h[j].size > 1
        # merge the two sub arrays
        array[h[j][0]].replace((array[h[j][0]] | array[h[j][1]]).sort)
        array.delete_at(h[j][1])
        return reduce(array)
        # recurse until nothing needs to be merged
      end
    end
  end
  array
end

puts reduce(a).to_s #[["A", "B", "C", "D", "E", "F", "G"]]
puts reduce(b).to_s #[["A", "B", "C", "D", "E", "F"], ["G", "H"]]

这是我的 快的 我确定可以优化的版本:)

# array = [["B", "C", "E", "F"], ["A", "B", "C", "D"], ["G"]]
# array = [["B", "C", "E", "F"], ["A", "B", "C", "D"], ["F", "G"]]
array = [["B", "C", "E", "F"], ["A", "B", "C", "D"], ["G"], ["G", "H"]]

array.collect! do |e|
  t = e
  e.each do |f|
    array.each do |a|
      if a.index(f)
        t = t | a
      end
    end
  end
  e = t.sort
end

p array.uniq

不同的算法,使用“边走边合并”方法,而不是在数组上进行两次传递(模糊地受联合查找算法的影响)。感谢您的有趣问题:)

A = [["A", "G"],["B", "C", "E", "F"], ["A", "B", "C", "D"], ["B"], ["H", "I"]]
H = {}
B = (0...(A.length)).to_a

def merge(i,j)
  A[j].each do |e|
    if H[e] and H[e] != j
      merge(i, H[e])
    else
      H[e] = i
    end
  end

  A[i] |= A[j]
  B[j] = i
end

A.each_with_index do |x, i| 
  min = A.length
  x.each do |j| 
    if H[j]
      merge(H[j], i)
    else
      H[j] = i
    end
  end
end

out = B.sort.uniq.map {|i| A[i]}
p out

不是最简单的,可能是最长的。)

l = [["B", "C", "E", "F"], ["A", "B", "C", "D"], ["G"]]
puts l.flatten.inject([[],[]])  {|r,e| if l.inject(0) {|c,a| if a.include?(e) then c+1 else c end} >= 2 then r[0] << e ; r[0].uniq! else r[1] << e end ; r}.inspect
#[["B", "C"], ["E", "F", "A", "D", "G"]]

 l = [["B", "C", "E", "F"], ["A", "B","C", "D"], ["G"]] 
 p l.inject([]){|r,e|
     r.select{|i|i&e!=[]}==[]&&(r+=[e])||(r=r.map{|i|(i&e)!=nil&&(i|e).sort||i})
 }

我不确定你的状况。

最简单的方法是获取数组的幂集(包含数组元素的每个可能组合的集合),如果没有公共元素,则抛出任何结果集,平展其余的集合,并丢弃子集和重复项。

或者至少如果Ruby有适当的设置支持的话。实际上,在Ruby中这样做效率极低,而且是一种糟糕的拼凑:

power_set = array.inject([[]]){|c,y|r=[];c.each{|i|r<<i;r<<i+[y]};r}.reject{|x| x.empty?}
collected_powerset = power_set.collect{|subset| subset.flatten.uniq.sort unless
  subset.inject(subset.last){|acc,a| acc & a}.empty?}.uniq.compact

collected_powerset.reject{|x| collected_powerset.any?{|c| (c & x) == x && x.length < c.length}}

动力装置操作来自 here .

直截了当而不是聪明。它破坏了原来的阵列。基本理念是:

• 向下搜索数组列表,注意每个元素出现在哪个数组中
• 对于此索引列表中显示多个数组中的元素的每个条目,将所有这些数组合并到最低的索引数组中。
• 合并两个数组时,用合并结果替换下索引数组,用指向下索引数组的指针替换上索引数组。

虽然实际的运行速度将取决于Ruby向C层交付的内容,但与每对数组相交相比,它在算法上要便宜得多。

a = [["B", "C", "E", "F"], ["A", "B", "C", "D"], ["G"], ["G", "H"]]

h = Hash.new {|h,k| h[k] = []}
a.each_with_index {|x, i| x.each {|j| h[j] << i}}
b = (0...(a.length)).to_a
h.each_value do |x| 
  x = x.sort_by {|i| b[i]}
  if x.length > 1
    x[1..-1].each do |i| 
      b[i] = [b[i], b[x[0]]].min
      a[b[i]] |= a[i]
    end 
  end
end

a = b.sort.uniq.map {|i| a[i]}

def merge_intersecting(input, result=[])
  head = input.first
  tail = input[1..-1]
  return result if tail.empty?
  intersection = tail.select { |arr| !(head & arr).empty? }
  unless intersection.empty?
    merged = head | intersection.flatten
    result << merged.sort
  end
  merge_intersecting(tail, result)
end


require 'minitest/spec'
require 'minitest/autorun'

describe "" do
  it "merges input array" do
    input  = [["B", "C", "E", "F"], ["A", "B", "C", "D"], ["F", "G"]]
    output = [["A", "B", "C", "D", "E", "F", "G"]]
    merge_intersecting(input).must_equal output
  end
  it "merges input array" do
    input  = [["B", "C", "E", "F"], ["A", "B", "C", "D"], ["G"], ["G", "H"]]
    output = [["A", "B", "C", "D", "E", "F"], ["G", "H"]]
    merge_intersecting(input).must_equal output
  end
end