Пересечения массивов с повторяющимися элементами в Ruby

Question

Я хотел бы (быстро) определить, содержит ли один массив все элементы другого массива, принимая во внимание, что массивы могут иметь повторяющиеся элементы.

Таким образом, я пытался что-то вроде этого:

alice = %w(a a a b) 
bob = %w(a a b c d e) 
alice & bob => ["a", "b"] 
alice - bob => [] 

Но то, что я хотел бы это оператор, который позволит мне определить, что боб не включает в себя все элементы Алисе, потому что боб не хватает «a» персонажей.

Answer 1

alice.select{|x| alice.count(x) > bob.count(x)} 

Update Настройка тест:

require 'benchmark' 

def subset_multivalue?(a, b) 
    bb = b.clone 
    a.each do |e| 
    i = bb.index(e) 
    if i 
     bb.delete_at(i) 
    else 
     return false 
    end 
    end 
    return true 
end 

def subset_multivalue2?(a, b) 
    a.find{|x| a.count(x) > b.count(x)} 
end 

def subset_multivalue3?(alice, bob) 
    alice_counts = alice.each_with_object(Hash.new(0)) { |o, h| h[o] += 1 } 
    bob_counts = bob.each_with_object(Hash.new(0)) { |o, h| h[o] += 1 } 

    alice_counts.all? do |k, v| 
    bob_counts.has_key?(k) && bob_counts[k] >= v 
    end 
end 

alice = %w(a a a b) 
bob = %w(a a b c d e) 

Benchmark.bm do |x| 
    x.report("dave:") do 
    1000000.times do 
     subset_multivalue?(alice, bob) 
    end 
    end 

    x.report("me:") do 
    1000000.times do 
     subset_multivalue2?(alice,bob) 
    end 
    end 

    x.report("andrew:") do 
    1000000.times do 
     subset_multivalue3?(alice,bob) 
    end 
    end 
end 

Результаты:

 user  system  total  real 
dave: 15.054000 0.000000 15.054000 (15.108864) 
me: 11.529000 0.031000 11.560000 (11.689669) 
andrew: 65.036000 0.047000 65.083000 (67.463859) 

Answer 2

Вероятно, проще всего подсчитать, как часто каждый элемент происходит таким образом, мы не должны слишком беспокоиться о отслеживанием дублей мы/не посчитали:

alice_counts = alice.each_with_object(Hash.new(0)) { |o, h| h[o] += 1 } 
#=> {"a"=>3, "b"=>1} 

bob_counts = bob.each_with_object(Hash.new(0)) { |o, h| h[o] += 1 } 
#=> {"a"=>2, "b"=>1, "c"=>1, "d"=>1, "e"=>1} 

Затем убедитесь, что каждый ключ в alice_counts имеет значение, равное или большее в bob_counts:

alice_counts.all? { |k, v| bob_counts[k] >= v } 
#=> false 

Answer 3

Я думаю, я остановился на этом:

def subset_multivalue?(a, b) 
    bb = b.clone 
    a.each do |e| 
      i = bb.index(e) 
      if i 
        bb.delete_at(i) 
      else 
        return false 
      end 
    end 
    return true 
end 

Я понимаю, что он не очень рубиновый, но он, похоже, выполняет эту работу.

Answer 4

Перечислимый # group_by() будет выбором.

alice = %w(a a a b) 
bob = %w(a a b c d e) 
alice_group = alice.group_by{|a| a}.map{|k,v| [k ,v.length]} 
#=> [["a", 3], ["b", 1]] 
bob_group = bob.group_by{|a| a}.map{|k,v| [k ,v.length]} 
#=> [["a", 2], ["b", 1], ["c", 1], ["d", 1], ["e", 1]] 
alice_group-bob_group 
#=> [["a", 3]] 
bob_group-alice_group 
#=>[["a", 2], ["c", 1], ["d", 1], ["e", 1]]