Руби, убери супер-массивы

Question

Если у меня есть массив массивов A, и я хочу избавиться от всех массивов в A, у которых также есть подмассив в A, как бы я это сделал?В этом контексте array_1 является подмассивом array_2, если array_1 - array_2 = [].В случае, если несколько массивов являются просто переставленными версиями одних и тех же элементов, начисляются бонусные баллы, если вы можете избавиться от всех, кроме одного, но вы можете справиться с этим так, как хотите, если это проще.

В python,Я мог бы легко использовать понимание, с A набором замороженных наборов:

A = {a for a in A if all(b-a for b in A-{a})}

Есть ли простой способ написать это в ruby?Мне все равно, если порядок A или его массивы сохраняются вообще.Кроме того, в моей программе ни один из массивов не имеет повторяющихся элементов, если это облегчает / ускоряет процесс.

Пример

A = [[1,6],[1,2],[2,4],[3,5],[1,3,6],[2,3,6]] 
# [1,6] is a subarray of [1,3,6], so [1,3,6] should be removed
remove_super_arrays(A) 
> A = [[1,6],[1,2],[2,4],[3,5],[2,3,6]] 

A = [[1,2,4],[2,3,4],[1,4,5],[2,6]]
# although there is overlap, there are no subarrays, so nothing should be removed
remove_super_arrays(A)
> A = [[1,2,4],[2,3,4],[1,4,5],[2,6]]

A = [[1],[2,1,3],[2,4],[1,4]]
# [1] is a subarray of [2,1,3] and [1,4]
remove_super_arrays(A)
> A = [[1],[2,4]]

Answer 1

Код

def remove_super_arrays(arr)
  order = arr.each_with_index.to_a.to_h
  arr.sort_by(&:size).reject.with_index do |a,i|
    arr[0,i].any? { |aa| (aa.size < a.size) && (aa-a).empty? }
  end.sort_by { |a| order[a] }
end

Примеры

remove_super_arrays([[1,6],[1,2],[2,4],[3,5],[1,3,6],[2,3,6]] ) 
  #=> [[1,6],[1,2],[2,4],[3,5],[2,3,6]]

remove_super_arrays([[1,2,4],[2,3,4],[1,4,5],[2,6]])
  #=> [[1,2,4],[2,3,4],[1,4,5],[2,6]]

remove_super_arrays([[1],[2,1,3],[2,4],[1,4]])
  #=> [[1],[2,4]]

Пояснение

Рассмотримпервый пример.

arr = [[1,6],[1,2],[2,4],[3,5],[1,3,6],[2,3,6]]

Сначала мы сохраняем позиции элементов a

order = arr.each_with_index.to_a.to_h # save original order
  #=> {[1, 6]=>0, [1, 2]=>1, [2, 4]=>2, [3, 5]=>3, [1, 3, 6]=>4, [2, 3, 6]=>5}

Затем отклоняем элементы arr:

b = arr.sort_by(&:size)
  #=> [[1, 6], [1, 2], [2, 4], [3, 5], [1, 3, 6], [2, 3, 6]]
c = b.reject.with_index do |a,i|
  arr[0,i].any? { |aa| (aa.size < a.size) && (aa-a).empty? }
end
  #=> [[1, 6], [1, 2], [2, 4], [3, 5], [2, 3, 6]] 

Наконец, измените порядок c, чтобы он соответствовал исходному порядку элементов arr.

c.sort_by { |a| order[a] }
  #=> [[1, 6], [1, 2], [2, 4], [3, 5], [2, 3, 6]]

, который в данном случае соответствует порядку элементов c.

.

Давайте более внимательно посмотрим на вычисление c:

enum1 = b.reject
  #=> #<Enumerator: [[1, 6], [1, 2], [2, 4], [3, 5], [1, 3, 6],
  #     [2, 3, 6]]:reject> 
enum2 = enum1.with_index
  #=> #<Enumerator: #<Enumerator: [[1, 6], [1, 2], [2, 4], [3, 5],
  #     [1, 3, 6], [2, 3, 6]]:reject>:with_index> 

Первый элемент генерируется перечислителем enum2 и передается в блок и присваивается в качестве значений переменных блока:

a, i = enum2.next
  #=> [[1, 6], 0] 
a #=> [1, 6] 
i #=> 0 

Затем выполняется расчет блока:

d = arr[0,i]
  #=> [] 
d.any? { |aa| (aa.size < a.size) && (aa-a).empty? }
  #=> false 

, поэтому a[0] не отклоняется.Следующая пара, переданная блоку enum2, равна [[1, 2], 1].Это значение также сохраняется, но давайте перейдем к последнему элементу, переданному блоку, на enum2:

a, i = enum2.next
  #=> [[1, 2], 1] 
a, i = enum2.next
  #=> [[2, 4], 2] 
a, i = enum2.next
  #=> [[3, 5], 3]

a, i = enum2.next
  #=> [[1, 3, 6], 4] 
a #=> [1, 3, 6]
i #=> 4 

ВыполнитеРасчет блока:

d = arr[0,i]
  #=> [[1, 6], [1, 2], [2, 4], [3, 5]] 
d.any? { |aa| (aa.size < a.size) && (aa-a).empty? }
  #=> true 

При возвращении true, a отклоняется.В последнем вычислении первый элемент d передается в блок, и выполняется следующее вычисление:

aa = [1, 6]
(aa.size < a.size)
  #=> 2 < 3 => true
(aa-a).empty?
  #=> ([1, 6] - [1, 3, 6]).empty? => [].empty? => true

При true && true #=> true, a ([1, 3, 6]) отклоняется.

Альтернативный расчет

Ниже приведено более точное соответствие с эквивалентом Python для OP, но оно менее эффективно:

def remove_super_arrays(arr)
  arr.select do |a|
    (arr-[a]).all? { |aa| aa.size > a.size || (aa-a).any? }
  end
end

или

def remove_super_arrays(arr)
  arr.reject do |a|
    (arr-[a]).any? { |aa| (aa.size < a.size) && (aa-a).empty? }
  end
end

Answer 2

Это было хорошее упражнение для меня.Я использовал логику из здесь .

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

def remove_super_arrays(arr)
  arr.each_with_index.with_object([]) do |(sub_array, index), result|
    next if index == 0
    result << sub_array unless (arr.first - sub_array).empty?
  end.unshift(arr.first)
end

arr = [[1,6],[1,2],[2,4],[3,5],[1,3,6],[2,3,6]]   
p remove_super_arrays(arr)  
 #=> [[1, 6], [1, 2], [2, 4], [3, 5], [2, 3, 6]]