确定一个数组是否包含另一个数组的所有元素

Question

我需要判断一个数组是否包含另一个数组的重复元素。

[1,2,3].contains_all? [1,2]   #=> true
[1,2,3].contains_all? [1,2,2] #=> false (this is where (a1-a2).empty? fails)
[2,1,2,3].contains_all? [1,2,2] #=> true

因此，第一个数组必须包含第二个数组中每个唯一元素的数量相等或不少于其数量。

对于使用数组作为集合的人，这个问题已经有了答案，但我需要控制重复项。

更新：基准测试

在 Ruby 1.9.3p194 上进行。

def bench
  puts Benchmark.measure {
    10000.times do
      [1,2,3].contains_all? [1,2]
      [1,2,3].contains_all? [1,2,2]
      [2,1,2,3].contains_all? [1,2,2]
    end
  }
end

结果为：

Rohit   0.100000   0.000000   0.100000 (  0.104486)
Chris   0.040000   0.000000   0.040000 (  0.040178)
Sergio  0.160000   0.020000   0.180000 (  0.173940)
sawa    0.030000   0.000000   0.030000 (  0.032393)

更新2：更大的数组

@a1 = (1..10000).to_a
@a2 = (1..1000).to_a
@a3 = (1..2000).to_a

def bench
  puts Benchmark.measure {
    1000.times do
      @a1.contains_all? @a2
      @a1.contains_all? @a3
      @a3.contains_all? @a2
    end
  }
end

结果为：

Rohit    9.750000   0.410000  10.160000 ( 10.158182)
Chris   10.250000   0.180000  10.430000 ( 10.433797)
Sergio  14.570000   0.070000  14.640000 ( 14.637870)
sawa     3.460000   0.020000   3.480000 (  3.475513)

- Chris

---

你应该针对更大的数组进行基准测试。（除非它在你的使用情况下始终很小） - rohit89

看起来@sawa的答案在处理大型数组方面确实是最好的，但我永远不会有那么大的数组。无论如何，sawa的实现目前似乎是最好的。 - Chris

如果你反过来写，像 @a2.contains_all? @a1，基于哈希的答案会更快。虽然对于小数组来说，无论哪种方式都没有太大影响。 - rohit89

你可能会添加一个检查来确保另一个数组更小（不可能返回true），这样情况对于所有的时间都是恒定的。 - Chris

Answer 1

class Array
  def contains_all? other
    other = other.dup
    each{|e| if i = other.index(e) then other.delete_at(i) end}
    other.empty?
  end
end

- sawa

---

不错！看起来是迄今为止最好的。 - Chris

Answer 2

这是一个天真而直接的实现（可能不是最有效的）。只需计算元素并比较元素及其出现次数即可。

class Array
  def contains_all? ary
    # group the arrays, so that 
    #   [2, 1, 1, 3] becomes {1 => 2, 2 => 1, 3 => 1}
    my_groups = group_and_count self
    their_groups = group_and_count ary

    their_groups.each do |el, cnt|
      if !my_groups[el] || my_groups[el] < cnt
        return false
      end
    end

    true
  end

  private
  def group_and_count ary
    ary.reduce({}) do |memo, el|
      memo[el] ||= 0
      memo[el] += 1
      memo
    end
  end

end

[1, 2, 3].contains_all? [1, 2]   # => true
[1, 2, 3].contains_all? [1, 2, 2] # => false
[2, 1, 2, 3].contains_all? [1, 2, 2] # => true
[1, 2, 3].contains_all? [] # => true
[].contains_all? [1, 2] # => false

- Sergio Tulentsev

Answer 3

看起来你需要一个multiset。请查看这个gem，我认为它可以满足你的需求。

你可以使用它并执行以下操作（如果交集等于第二个multiset，则第一个包含所有元素）：

@ms1 & @ms2 == @ms2

- davidrac

Answer 4

class Array
  def contains_all?(ary)
    ary.uniq.all? { |x| count(x) >= ary.count(x) }
  end
end

测试

irb(main):131:0> %w[a b c c].contains_all? %w[a b c]
=> true
irb(main):132:0> %w[a b c c].contains_all? %w[a b c c]
=> true
irb(main):133:0> %w[a b c c].contains_all? %w[a b c c c]
=> false
irb(main):134:0> %w[a b c c].contains_all? %w[a]
=> true
irb(main):135:0> %w[a b c c].contains_all? %w[x]
=> false
irb(main):136:0> %w[a b c c].contains_all? %w[]
=> true

以下版本的代码更快且更简短。

class Array
  def contains_all?(ary)
    ary.all? { |x| count(x) >= ary.count(x) }
  end
end

- Zack Xu

Answer 5

计算出现次数并进行比较似乎是显而易见的方法。

class Array
   def contains_all? arr
       h = self.inject(Hash.new(0)) {|h, i| h[i] += 1; h}
       arr.each do |i|
           return false unless h.has_key?(i)
           return false if h[i] == 0
           h[i] -= 1
       end
       true
   end
end

- rohit89

---

如果您关心速度，将== 0更改为zero?会略微提高速度。 - sawa

Answer 6

分享我的实现方式，但是我一定想看看是否有人能够提出更高效的方法。（我不会接受自己的答案）

class Array
  def contains_all?(a2)
    a2.inject(self.dup) do |copy, el|
      if copy.include? el
        index = copy.index el
        copy.delete_at index
      else
        return false
      end
      copy
    end
    true
  end
end

还有测试：

1.9.3p194 :016 > [1,2,3].contains_all? [1,2]   #=> true
 => true 
1.9.3p194 :017 > [1,2,3].contains_all? [1,2,2] #=> false (this is where (a1-a2).empty? fails)
 => false 
1.9.3p194 :018 > [2,1,2,3].contains_all? [1,2,2] #=> true
 => true 

- Chris

---

据我所知，Array#index和Array#include?的时间复杂度为O(n)。每次调用都需要迭代整个数组。因此，如果您有大型数组，这可能会带来问题。当contains=false时，您可以跳出循环。 - rohit89

Answer 7

这个解决方案只会遍历两个列表一次，因此运行时间是线性的。但如果预计列表非常小，则可能会有太多开销。

  class Array
    def contains_all?(other)
      return false if other.size > size
      elem_counts = other.each_with_object(Hash.new(0)) { |elem,hash| hash[elem] += 1 }
      each do |elem|
        elem_counts.delete(elem) if (elem_counts[elem] -= 1) <= 0
        return true if elem_counts.empty?
      end
      false
    end
  end

- Joel

Answer 8

如果找不到方法，可以使用 Ruby 的 include? 方法构建一个。

官方文档：http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-include-3F 用法：

array = [1, 2, 3, 4]
array.include? 3       #=> true

然后，你可以进行一个循环：

def array_includes_all?( array, comparision_array )
  contains = true
  for i in comparision_array do
    unless array.include? i
      contains = false
    end
  end
  return contains
end

array_includes_all?( [1,2,3,2], [1,2,2] )    #=> true

- macool

---

但是，array_includes_all？([1,2,3]，[1,2,2,2])也将为真，因为include？(2)将继续找到相同的2。 - Chris

你的代码在 OP 的第二个示例上失败了。它返回 true，但应该返回 false。 - Sergio Tulentsev

对不起，我想我误解了问题。 - macool