使用二维数组中最大数量的元素找到一个非空交集

Question

我有一个二维数组:

   keys = [[:reference],
     [:parent_ref, :kind],
     [:kind, :parent_ref, :reference],
     [:parent_ref, :kind, :status]]

假设我想要这些数组的交集。我可以这样做：

keys.reduce{|arr, acc| arr & acc}

由于没有普遍的公共键，这将导致[]。现在假设我想使用数组中最大数量的元素来查找“非空交集”。例如，使用此“方法”的交集将是[: parent_ref，: kind]，因为它是交集。

[[:parent_ref, :kind],
         [:kind, :parent_ref, :reference],
         [:parent_ref, :kind, :status]]

我们只需要把[:reference]放在一边。

你将如何处理/创建这样的算法。

- David Geismar

---

我不确定我是否理解了问题和你的例子。你所说的“使用最大数量的元素”是什么意思？你能用另一种方式解释一下吗？ - Stefan

在我看来，在这种情况下，元素就是内部数组。因此，他正在寻找涉及数组数量最多的交集。请参见此示例中的红色部分：https://i.imgur.com/bxLBqf3.png - claasic

Answer 1

暴力破解，使用排列：

keys.combination(2).map { |a, b| a & b }.max_by(&:size)
#=> [:parent_ref, :kind]

找到使用的元素，也可以使用蛮力方法：

res = [:parent_ref, :kind]
keys.select { |e| e.sort & res.sort == res.sort }
#=> [[:parent_ref, :kind], [:kind, :parent_ref, :reference], [:parent_ref, :kind, :status]]

- iGian

Answer 2

假设二维数组是一个字符串数组，其中每个字符串都是字符数组。 假设我们有以下字符串：

CDB
BC
CBA
FDE
EDBC

首先将每个字符串按照升序排序。

BCD
BC
ABC
DEF
BCDE

然后对字符串进行排序。

ABC
BC
BCD
BCDE
DEF

对于每个元素，找出出现在最长连续字符串序列中的元素。在我们的例子中，应该是 B 和 C。它们的连续字符串是具有非空交集的字符串数量最多的。

- RobertBaron

Answer 3

我相信你的问题与这个有关，这个答案是相关的。

为了更易读，你可以将输入转换为较短的名称：

matrix = [[:a], [:b, :c], [:c, :b, :a], [:b, :c, :d]]

您可以遍历这些值，并保持一个哈希表，其中包含每个值所在的所有集合：

matrix.each.with_index(1) do |row, i|
  row.each do |value|
    grouped_values[value] << i
  end
end

p grouped_values
# => {:a=>[1, 3], :b=>[2, 3, 4], :c=>[2, 3, 4], :d=>[4]}

因此，集合1和3中都存在:a，集合2、3和4中存在b...

然后您可以将这些集合分组在一起：

grouped_sets = Hash.new{|h, k| h[k] = []}

grouped_values.each do |value, sets|
  grouped_sets[sets] << value if sets.size > 1
end

p grouped_sets
# => {[1, 3]=>[:a], [2, 3, 4]=>[:b, :c]}

因此，集合1和3的交集是[:a]，而集合2、3和4的交集是[:b, :c]。

最后，您可以选择具有最多集合或最多元素的交集。

- Eric Duminil

---

我认为你在这里缺少了一些交集：比如说你有b=>[2,3,4]和 c=>[2,3,4,5]，这个解决方案将会错过[2,3,4] => [:b, :c]。 - David Geismar

@DavidGeismar：看起来你是对的。它找到的是与最多子集的交集，而不是与最多元素的交集。 - Eric Duminil

Answer 4

arr = [
  [:reference],
  [:parent_ref, :kind],
  [:kind, :parent_ref, :reference],
  [:parent_ref, :kind],
  [:parent_ref, :kind, :status],
  [:kind, :parent_ref, :kind]
]

请注意，我已经修改了示例中给出的keys，以包括两种类型的重复项。

require 'set'

h = arr.each_with_object(Hash.new { |h,k| h[k] = [] }) { |a,h| h[a.to_set] << a }
  #=> {#<Set: {:reference}>=>[[:reference]],
  #    #<Set: {:parent_ref, :kind}>=>[[:parent_ref, :kind],
  #             [:parent_ref, :kind], [:kind, :parent_ref, :kind]],
  #    #<Set: {:kind, :parent_ref, :reference}>=>[[:kind, :parent_ref, :reference]],
  #    #<Set: {:parent_ref, :kind, :status}>=>[[:parent_ref, :kind, :status]]} 
g = h.each_key.with_object({}) do |k,g|
  g[k] = h[k].dup
  h.each { |kk,v| g[k].concat(v) if k < kk }
end 
  #=> {#<Set: {:reference}>=>[[:reference], [:kind, :parent_ref, :reference]],
  #    #<Set: {:parent_ref, :kind}>=>[[:parent_ref, :kind], [:parent_ref, :kind],
  #             [:kind, :parent_ref, :kind], [:kind, :parent_ref, :reference],
  #             [:parent_ref, :kind, :status]],
  #    #<Set: {:kind, :parent_ref, :reference}>=>[[:kind, :parent_ref, :reference]],
  #    #<Set: {:parent_ref, :kind, :status}>=>[[:parent_ref, :kind, :status]]} 
a = g.max_by { |k,v| v.size }
  #=> [#<Set: {:parent_ref, :kind}>, [[:parent_ref, :kind], [:parent_ref, :kind],
  #     [:kind, :parent_ref, :kind], [:kind, :parent_ref, :reference],
  #     [:parent_ref, :kind, :status]]] 
[a.last.first, a.last.drop(1)]
  #=> [[:parent_ref, :kind], [[:parent_ref, :kind], [:kind, :parent_ref, :kind],
  #    [:kind, :parent_ref, :reference], [:parent_ref, :kind, :status]]]

这显示了数组[:parent_ref, :kind]，在转换为集合后，是以下其他元素的子集array在转换为集合后：

[[:parent_ref, :kind], [:kind, :parent_ref, :kind],
 [:kind, :parent_ref, :reference], [:parent_ref, :kind, :status]]

并且在将arr的所有元素转换为集合后，没有其他元素具有更多的超集。

请注意，如果需要，可以链接g和a的计算。

请参见Set#<。

如果arr或arr的任何元素都不包含重复项，则计算当然会简化。

arr = [
  [:reference],
  [:parent_ref, :kind],
  [:kind, :parent_ref, :reference],
  [:parent_ref, :kind, :status]
]

require 'set'

sets = arr.map(&:to_set)
  #=> [#<Set: {:reference}>, #<Set: {:parent_ref, :kind}>,
  #    #<Set: {:kind, :parent_ref, :reference}>, #<Set: {:parent_ref, :kind, :status}>]
h = sets.each_with_object(Hash.new { |h,k| h[k] = [] }) { |s,h|
       sets.each { |ss| h[s] << ss if s < ss } }
  #=> {#<Set: {:reference}>=>[#<Set: {:kind, :parent_ref, :reference}>],
  #    #<Set: {:parent_ref, :kind}>=>[#<Set: {:kind, :parent_ref, :reference}>,
  #    #<Set: {:parent_ref, :kind, :status}>]}
k, v = h.max_by { |_,v| v.size }
  #=> [#<Set: {:parent_ref, :kind}>,
  #     [#<Set: {:kind, :parent_ref, :reference}>, #<Set: {:parent_ref, :kind, :status}>]]
[k.to_a, v.map(&:to_a)]
  #=> [[:parent_ref, :kind],
  #    [[:kind, :parent_ref, :reference], [:parent_ref, :kind, :status]]] 

- Cary Swoveland