确定一个数组是否包含另一个数组的所有元素
我需要告诉一个数组是否包含具有重复项的另一个数组的所有元素。
[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：更大的arrays
@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)
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
这是一个天真而直接的实现（可能不是最有效的实现）。 只计算元素并比较两个元素及其出现次数。
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
看来你需要一个multiset。 看看这个gem ，我认为它可以满足您的需求。
您可以使用is并执行类似的操作（如果交集等于第二个multiset，则第一个包含其所有元素）：
@ms1 & @ms2 == @ms2
计算出现次数并比较它们似乎是显而易见的方法。
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
回答我自己的实现，但绝对想看看是否有人能够提出一种更有效的方式。 （我不会接受我自己的回答）
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
此解决方案仅迭代两个列表一次，因此以线性时间运行。 但是，如果预计列表非常小，则可能会产生过多的开销。
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
class Array def contains_all?(ary) ary.uniq.all? { |x| count(x) >= ary.count(x) } end end
测试
irb(main):131:0> %w[abcc].contains_all? %w[abc] => true irb(main):132:0> %w[abcc].contains_all? %w[abcc] => true irb(main):133:0> %w[abcc].contains_all? %w[abccc] => false irb(main):134:0> %w[abcc].contains_all? %w[a] => true irb(main):135:0> %w[abcc].contains_all? %w[x] => false irb(main):136:0> %w[abcc].contains_all? %w[] => true
以下版本的代码更快更短。
class Array def contains_all?(ary) ary.all? { |x| count(x) >= ary.count(x) } end end
如果找不到方法，可以使用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