15

配列に重複のある別の配列のすべての要素が含まれているかどうかを確認する必要があります。

[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

したがって、最初の配列には、2 番目の配列内の一意の各要素の数と同数または同じ数が含まれている必要があります。

この質問は、配列をセットとして使用している場合に回答しますが、重複を制御する必要があります。

更新: ベンチマーク

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)
4

8 に答える 8

6 
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
于 2012-11-25T18:44:30.997 に答える
2

マルチセットが必要なようです。この宝石をチェックしてください。必要なことはできると思います。

is を使用して、次のようなことを行うことができます (交差が 2 番目の multiset と等しい場合、最初の multiset にはすべての要素が含まれます)。

@ms1 & @ms2 == @ms2
于 2012-11-25T18:44:34.820 に答える
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
于 2012-11-25T18:14:28.370 に答える
1

出現回数を数えて比較するのが当然の方法のようです。 

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
于 2012-11-25T18:25:04.910 に答える
0

私自身の実装で回答していますが、誰かがより効率的な方法を思い付くことができるかどうかを確認したい. （私は自分の答えを受け入れません）

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
于 2012-11-25T18:30:00.100 に答える
0

このソリューションは、両方のリストを一度だけ反復するため、線形時間で実行されます。ただし、リストが非常に小さいと予想される場合は、オーバーヘッドが大きすぎる可能性があります。

  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
于 2012-11-26T08:32:34.437 に答える
-1

メソッドが見つからない場合は、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
于 2012-11-25T18:16:03.173 に答える