Ruby трехстороннее транзитивное сравнение

Question

Я хочу сравнить три массива транзитивно, чтобы увидеть, есть ли какие-либо общие элементы:

arrs = [
["AAA", "", ""],
["", "", "CCC"],
["AAA", "BBB", "CCC"]
]

Я хочу вернуть матрицу, которая сравнивает элементы транзитивно. То есть, если два массива совместно используют один и тот же элемент или если они совпадают с третьей записью, верните 1. В противном случае верните 0.

. В этом примере результат должен быть:

result = [
[1, 1, 1],
[1, 1, 1],
[1, 1, 1]
]

result[0][0] равно 1, потому что если мы сравним arrs[0] с arrs[0] (сравните себя ), они разделяют "AAA".

result[0][1] - это 1, потому что если мы сравним arrs[0] и arrs[1], то нет общих элементов, но оба arrs[0] & arrs[2] и arrs[1] & arrs[2] возвращают пересекающиеся элемент, поэтому мы возвращаем 1

result[0][2] равно 1, потому что если мы сравним arrs[0] с arrs[2], они получат "AAA"

Мы повторяем процесс для всех другие комбинации массивов в arrs.

Answer 1

Это действительно не так сложно, вам просто нужно удвоить- map здесь:

def transitive(arr)
  arr.map do |a|
    arr.map do |b|
      (a & b).any? ? 1 : 0
    end
  end
end

Более Ruby подход заключается в использовании true или false, но 1 и 0 хорошо, если вы можете обработать троичную форму для ее преобразования.

Как это работает:

arrs = [
  ["AAA", "", ""],
  ["", "", "CCC"],
  ["AAA", "BBB", "CCC"]
]

transitive(arrs)
# => [[1, 1, 1], [1, 1, 1], [1, 1, 1]]

Не очень захватывающий пример. Вот тот, который имеет больше разнообразия:

arrs = [
  %w[ A B C ],
  %w[ A D E ],
  %w[ D E F ]
]

transitive(arrs)
# => [[1, 1, 0], [1, 1, 1], [0, 1, 1]]

Где это имеет некоторые промахи.

Answer 2

Предположение

Нам дан массив arr размера n, каждый элемент является массивом размера m. Мы sh создадим другой массив n x m, a, такой что каждый элемент a[i][j] равен 1 (иначе 0), если все следующие массивы не пустые:

a[i] & a[i] #  non-empty if a is non-empty
a[i] & a[(i+1)%n]
a[(i+1)%n] & a[(i+2)%n]
a[(j-1)%n] & a[j]

Это то, что я понимаю как «переходный». Обратите внимание, что я предположил, что переходное отношение «оборачивается» от последнего к первому элементу arr.

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

arr = [["A", "B", "C"],
       ["A", "D", "E"],
       ["D", "E", "F"]]

Предположим, что мы будем sh для вычисления a[i][j] массива a, который создается. Это равняется 1 (иначе 0), если все следующие массивы не пустые:

a[1] & a[1]             #=> a[1]        => ["A", "D", "E"]
a[1] & a[2%3]           #=> a[1] & a[2] => ["D"] 
a[(i+1)%n] & a[(i+2)%n] #=> a[2] & a[1] => []

Обратите внимание, что имеет (a[1] & a[2%3]).empty? #=> true, нет необходимости вычислять третье выражение (или любое другое следующие выражения, если arr были больше).

Для i #=> 0,

a[0,0] = (arr[0] & arr[0]).any?
  #=> arr[0].any? #=> true, hence = 1
a[0,1] = (arr[0] & arr[1]).any?
  #=> ["A"].any? #=> true, hence = 1
a[0,2] = (arr[0] & arr[1]).any? && (arr[1] & arr[2]).any?
  #=> (a[0,1] == 1) && ["D"].any? => true && true => true, hence = 1

Для i #=> 1,

a[1,1] = (arr[1] & arr[1]).any?
  #=> arr[1].any? #=> true, hence = 1
a[1,2] = (arr[1] & arr[2]).any?
  #=> ["D"].any? #=> true, hence = 1
a[1,0] = (arr[1] & arr[2]).any? && (arr[2] & arr[0]).any?
  #=> (a[1,2] == 1) && [].any? => true && false => true, hence = 0

Для i #=> 2,

a[2,2] = (arr[2] & arr[2]).any?
  #=> arr[2].any? #=> true, hence = 1
a[2,0] = (arr[2] & arr[0]).any?
  #=> [].any? #=> false, hence = 0
a[2,1] = (arr[2] & arr[0]).any? && (arr[0] & arr[1]).any?
  #=> (a[2,0] == 1) && ["A"].any? => false && true => false, hence = 0

Код

require 'set'

def transitive(arr)
  n = arr.size
  st = n.times.with_object(Set.new) do |i,st|
       (i..i+n-1).each do |j|
         if j==i
           st << [i,j]
         else
           jj = j % n
           jprev = (j-1) % n
           break unless st.include?([i,jprev]) & (arr[jprev] & arr[jj]).any?
           st << [i,jj]
         end
       end
     end
  Array.new(n) do |i|
    Array.new(arr.first.size) { |j| st.include?([i,j]) ? 1 : 0 }
  end
end

Пример

Для arr, определенного ранее,

transitive(arr)
  #=> [[1, 1, 1],
  #    [0, 1, 1],
  #    [0, 0, 1]] 

Пояснение

Шаги следующие:

n = arr.size
  #=> 3
st = n.times.with_object(Set.new) do |i,st|
       (i..i+n-1).each do |j|
         if j==i
           st << [i,j]
         else
           jj = j % n
           jprev = (j-1) % n
           break unless st.include?([i,jprev]) & (arr[jprev] & arr[jj]).any?
           st << [i,jj]
         end
       end
     end
  #=> #<Set: {[0, 0], [0, 1], [0, 2], [1, 1], [1, 2], [2, 2]}>

st - это набор переходных элементов arr. Это показывает, что элементы arr с индексами [0, 2] (порядок имеет значение) являются переходными, а элементы с индексами [2, 0] - нет (поскольку st не содержит [2, 0]). Обратите внимание, что как только [2, 0] было определено, что оно не является транзитивным, нет необходимости проверять [2, 1].

На последнем шаге используется метод Array :: new :

Array.new(n) {|i| Array.new(arr.first.size) {|j| st.include?([i,j]) ? 1 : 0}}
  #=> [[1, 1, 1],
  #    [0, 1, 1],
  #    [0, 0, 1]]