Ruby中处理有重复元素的集合的交集和并集

Question

我们如何在Ruby中获取重复元素的集合的交集和并集。

# given the sets
a = ["A", "B", "B", "C", "D", "D"]
b = ["B", "C", "D", "D", "D", "E"]

# A union function that adds repetitions
union(a, b)
=> ["A", "B", "B", "C", "D", "D", "D", "E"]

# An intersection function that adds repetitions
intersection(a, b)
=> ["B", "C", "D", "D"]

&和|运算符似乎会忽略重复和重复项，这是根据文档中的描述。

# union without duplicates
a | b
=> ["A", "B", "C", "D", "E"]

# intersections without duplicates
a & b
=> ["B", "C", "D"]

- Amin Shah Gilani

---

根据数组文档，& 和 | 看起来会忽略重复元素。 - the Tin Man

在数学中，集合是一组不同对象的集合。 - steenslag

我猜你想知道如何实现你的方法union和intersection，如果是这样，请明确说明。它们与Array#|或Array#&无关，因此提到它们并没有什么帮助。示例很好，但它们并不能解释你想要你的方法表现出的精确行为。我们可以猜测，但可能会出错。你需要用文字描述这些行为；示例是次要的。 - Cary Swoveland

@CarySwoveland 我从来没有想过以那种方式看待它。我认为联合的定义是众所周知的，但用那种方式描述它实际上使其更容易实现，谢谢！ - Amin Shah Gilani

这是个很好的观点：一旦你准确地表达了问题，获得解决方案就只不过是将你的话转化为代码。 - Cary Swoveland

Answer 1

def union(a,b)
  (a|b).flat_map { |s| [s]*[a.count(s), b.count(s)].max }
end

union(a,b)
  # => ["A", "B", "B", "C", "D", "D", "D", "E"] 

def intersection(a,b)
  (a|b).flat_map { |s| [s]*[a.count(s), b.count(s)].min }
end

intersection(a,b)
  #=> ["B", "C", "D", "D"]

- Cary Swoveland

---

哇，非常简洁的解决方案！ - Stefan

Answer 2

在 Cary Swoveland's answer 的基础上，您可以创建一个临时哈希表来计算每个数组成员的出现次数：（我已经将参数数量通用化）

def multiplicities(*arrays)
  m = Hash.new { |h, k| h[k] = Array.new(arrays.size, 0) }
  arrays.each_with_index { |ary, idx| ary.each { |x| m[x][idx] += 1 } }
  m
end

multiplicities(a, b)
#=> {"A"=>[1, 0], "B"=>[2, 1], "C"=>[1, 1], "D"=>[2, 3], "E"=>[0, 1]}

实现union和intersection很简单：

def union(*arrays)
  multiplicities(*arrays).flat_map { |x, m| Array.new(m.max, x) }
end

def intersection(*arrays)
  multiplicities(*arrays).flat_map { |x, m| Array.new(m.min, x) }
end

union(a, b)        #=> ["A", "B", "B", "C", "D", "D", "D", "E"]
intersection(a, b) #=> ["B", "C", "D", "D"]

采用这种方法，每个数组只需要遍历一次。

- Stefan