Найти непустое пересечение, используя максимальное количество элементов в двумерном массиве

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] в сторону.

КакВы бы подошли / создали такой алгоритм.

Answer 1

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 (после того, как все элементы arr преобразованы в наборы) не имеет большего числа надмножеств.

Обратите внимание, что при желании вычисления g и a могут быть объединены в цепочку.

См. Set # <</a>.

Если ни 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]]] 

Answer 2

Предположим, что двумерный массив представляет собой массив строк, где каждая строка представляет собой массив символов. Предположим, у нас есть строки:

CDB
BC
CBA
FDE
EDBC

Сначала отсортируйте каждую строку в порядке возрастания.

BCD
BC
ABC
DEF
BCDE

Затем отсортируйте строки.

ABC
BC
BCD
BCDE
DEF

Для каждого элемента найдите элемент, который появляется в самой длинной последовательности последовательных строк. В нашем примере это были бы B и C. Их последовательные строки - это наибольшее количество строк с непустым пересечением.

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]}

Так что :a присутствует в наборах 1 и 3, b в наборах 2, 3 и 4 ...

Затем можно сгруппировать наборы:

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].

Наконец, вы можете выбрать пересечение с большинством наборов или с наибольшим количеством элементов.

Answer 4

Грубая сила, используя перестановки:

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]]