Как определить, содержит ли один массив все элементы другого массива

179

Дано:

a1 = [5, 1, 6, 14, 2, 8]

Я хотел бы определить, содержит ли он все элементы:

a2 = [2, 6, 15]

В этом случае результат false.

Существуют ли какие-либо встроенные методы Ruby / Rails для определения такого включения массива?

Один из способов реализовать это:

a2.index{ |x| !a1.include?(x) }.nil?

Есть ли лучший, более читаемый способ?

Миша Морошко
источник
Принятый ответ (вычитание массива) является самым быстрым решением. Я оценил
brainbag

Ответы:

309
a = [5, 1, 6, 14, 2, 8]
b = [2, 6, 15]

a - b
=> [5, 1, 14, 8]

b - a
=> [15]

(b - a).empty?
=> false
Geo
источник
61
Это путь. Это может быть немного сокращено до(a2-a1).empty?
Holger Just
9
Это работает только для массивов, которые являются наборами, но не для массивов с дубликатами
Chris
3
@Chris - Вы можете попробовать использовать Array # uniq для этого. С примером Хольгера Джаста это было бы(a2.uniq - a1.uniq).empty?
Ник
stackoverflow.com/questions/13553822/… вот что я имел ввиду. Массив # unique явно потерпит неудачу.
Крис
81

Возможно, это легче читать:

a2.all? { |e| a1.include?(e) }

Вы также можете использовать пересечение массива:

(a1 & a2).size == a1.size

Обратите внимание, что sizeздесь используется только для скорости, вы также можете сделать (медленнее):

(a1 & a2) == a1

Но я думаю, что первое более читабельно. Эти 3 - простые рубины (не рельсы).

Пабло Фернандес
источник
Если используется определение OP a1 и a2 и a1 ", содержащее все элементы" a2, я думаю, что это должно быть _ (a1 & a2) .size == a2.size _, поскольку a2 - это меньший массив, который должен иметь все элементы, включенные в больший массив (чтобы получить «истину») - следовательно, пересечение двух массивов должно быть той же длины, что и меньший массив, если все элементы в нем присутствуют в большем.
JosephK
57

Это может быть достигнуто путем

(a2 & a1) == a2

Это создает пересечение обоих массивов, возвращая все элементы из a2которых также находятся в a1. Если результат совпадает с a2, вы можете быть уверены, что все элементы включены в a1.

Этот подход работает только в том случае, если все элементы в a2первую очередь отличаются друг от друга. Если есть двойники, этот подход терпит неудачу. Тот из Tempos все еще работает тогда, поэтому я искренне рекомендую его подход (также он, вероятно, быстрее).

Хольгер Джаст
источник
2
использование lengthметода будет работать намного лучше
Пабло Фернандес
3
Это не будет работать, если набор пересечений имеет одинаковые элементы в другом порядке. Я нашел это трудным путем, пытаясь ответить на этот вопрос: stackoverflow.com/questions/12062970/… позже понял, что многие умные люди уже сделали это здесь!
CubaLibre
1
@CubaLibre Интересно. У вас есть тестовые данные, чтобы воспроизвести это? Из моих тестов казалось, что результирующий массив сохраняет порядок элементов из первого массива (отсюда мое последнее изменение моего ответа). Однако, если это действительно не так, я бы хотел узнать.
Хольгер, только
@HolgerПросто я сделал ошибку, выполнив (a1 & a2) вместо (a2 & a1), вот почему я видел ошибку. Вы правы и сохраняете порядок из первого массива.
CubaLibre
10

Если дублирующихся элементов нет или их не волнует, вы можете использовать класс Set :

a1 = Set.new [5, 1, 6, 14, 2, 8]
a2 = Set.new [2, 6, 15]
a1.subset?(a2)
=> false

За кулисами это использует

all? { |o| set.include?(o) }
Спутанность сознания
источник
1

Вы можете сделать мартовский патч для класса Array:

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
irb(main):137:0> %w[a b c d].contains_all? %w[d c h]
=> false
irb(main):138:0> %w[a b c d].contains_all? %w[d b c]
=> true

Конечно, метод может быть написан как стандартный метод, например

def contains_all?(a,b)
    b.uniq.all? { |x| a.count(x) >= b.count(x) }
end

и вы можете вызвать его как

contains_all?(%w[a b c c], %w[c c c])

Действительно, после профилирования следующая версия намного быстрее, а код короче.

def contains_all?(a,b)
    b.all? { |x| a.count(x) >= b.count(x) }
end
Зак Сюй
источник
0

В зависимости от размера ваших массивов, вы можете рассмотреть эффективный алгоритм O (n log n)

def equal_a(a1, a2)
  a1sorted = a1.sort
  a2sorted = a2.sort
  return false if a1.length != a2.length
  0.upto(a1.length - 1) do 
    |i| return false if a1sorted[i] != a2sorted[i]
  end
end

Сортировка стоит O (n log n), а проверка каждой пары стоит O (n), таким образом, этот алгоритм равен O (n log n). Другие алгоритмы не могут быть быстрее (асимптотически) с использованием несортированных массивов.

ayckoster
источник
Вы можете сделать это в O (n) с помощью счетной сортировки.
Клочнер
Нет, ты не можешь. Счетная сортировка использует ограниченную вселенную, и у Ruby нет ограничений на то, как большие числа могут быть получены.
Айкостер
Вы можете, потому что на самом деле вам не нужно сортировать элементы - вам просто нужен элемент отображения хеша -> счетчик для обоих массивов, затем итерации по ключам и сравнение счетчиков.
клочнер
Вы уверены, что Array # sort использует сортировку слиянием?
Нейт Симер
0

Большинство ответов, основанных на (a1 - a2) или (a1 & a2), не сработают, если в любом из этих массивов есть повторяющиеся элементы. Я прибыл сюда в поисках способа проверить, все ли буквы слова (разбитые на массивы) являются частью набора букв (например, для скрэббл). Ни один из этих ответов не сработал, но вот этот:

def contains_all?(a1, a2)
  try = a1.chars.all? do |letter|
    a1.count(letter) <= a2.count(letter)
  end
  return try
end
Чарльз Бретон
источник