ruby - Ruby，删除超级数组

Question

如果我有一个数组数组A，并且想要摆脱在A其中也有一个子数组的所有数组A，我该怎么做。在这种情况下，array_1是array_2if的子数组array_1 - array_2 = []。在多个数组只是相同元素的重新排列版本的情况下，如果您可以摆脱除其中一个之外的所有数组，则可以加分，但如果更容易，您可以随心所欲地处理它。

在 python 中，我可以很容易地使用理解，A作为一组冻结集：

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

有没有一种简单的方法可以用红宝石写这个？我不在乎是否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]]

标签： ruby

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]) 被拒绝。

替代计算

以下是与 OP 的 Python 等效项更接近的匹配，但效率较低：

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