Как получить общую последовательность (и) двух массивов?Рубин - PullRequest
Новая
       20

Как получить общую последовательность (и) двух массивов?Рубин

0 голосов
/ 25 июня 2018

Возвращает обычную самую длинную последовательность (и) элементов массива обоих массивов.Последовательность, включая дубликаты и расположенная в любом месте массива.

Например, я хочу получить подмножество [2,2,3], которое является общей последовательностью arr1 и arr2, используя минимальное количество кода (например,с операциями над множествами) в идеале без преобразования ints в strings

arr1 = [1,2,2,3,4]
arr2 = [5,2,2,3,6]
# common subset sequence is [2,2,3]

arr1 = [2,2,3,3,5]
arr1 = [3,3,2,2,5]
# common sequences are [2,2] [3,3]

1 Ответ

0 голосов
/ 26 июня 2018

Если n - это размер меньшего из двух массивов, следующий метод сначала вычисляет все последовательности длиной n для каждого массива, а затем определяет те последовательности в первом массиве, которые также появляются во втором массиве.Число таких общих последовательностей явно равно нулю или единице (последнее, потому что по крайней мере один из массивов имеет размер n).Если есть одна общая последовательность длины n, мы возвращаем массив, содержащий эту единственную последовательность, и мы закончим.

Если нет общих последовательностей длины n, мы повторяем процедуру для последовательностей длины n - 1.Если массив общих последовательностей длины n - 1 не пуст, мы возвращаем этот массив и завершаем работу;иначе мы повторяем для последовательностей длиной n - 2 и так далее.nil возвращается, если нет общих последовательностей длины 1.

Код 

def longest_common_sequences(arr1, arr2)
  [arr1.size, arr2.size].min.downto(0).each do |n|
    break nil if n.zero? 
    common = sequences_by_length(arr1, n) & sequences_by_length(arr2, n)
    break common unless common.empty?
  end         
end

def sequences_by_length(arr, n)
  arr.each_cons(n).to_a
end

Примеры 

longest_common_sequences [1,2,2,3,4], [5,2,2,3,6]
   #=> [[2, 2, 3]]

longest_common_sequences [2,2,3,3,5], [3,3,2,2,5]
  #=> [[2, 2], [3, 3]]

longest_common_sequences [1,2,3], [4,5,6]
  #=> nil

Пояснение

Я добавил puts операторов в тело longest_common_sequences, чтобы проиллюстрировать вычисления, выполненные методом для второго примера выше. 

arr1 = [2,2,3,3,5]
arr2 = [3,3,2,2,5]

t = [arr1.size, arr2.size].min
puts "[arr1.size, arr2.size].min = #{t}"
t.downto(0).each do |n|
  puts "n = #{n}"
  puts "break nil as #{n}.zero? #=> true" if n.zero?
  break nil if n.zero? 
  common = sequences_by_length(arr1, n) & sequences_by_length(arr2, n)
  puts "common = #{common}"
  break common unless common.empty?
end         

def sequences_by_length(arr, n)
  puts "  generate sequences of length #{n} for arr = #{arr}"
  a = arr.each_cons(n).to_a
  puts "  returning #{a}"
  a
end

печатает 

n = 5
  generate sequences of length 5 for arr = [2, 2, 3, 3, 5]
  returning [[2, 2, 3, 3, 5]]
  generate sequences of length 5 for arr = [3, 3, 2, 2, 5]
  returning [[3, 3, 2, 2, 5]]
common = []
n = 4
  generate sequences of length 4 for arr = [2, 2, 3, 3, 5]
  returning [[2, 2, 3, 3], [2, 3, 3, 5]]
  generate sequences of length 4 for arr = [3, 3, 2, 2, 5]
  returning [[3, 3, 2, 2], [3, 2, 2, 5]]
common = []
n = 3
  generate sequences of length 3 for arr = [2, 2, 3, 3, 5]
  returning [[2, 2, 3], [2, 3, 3], [3, 3, 5]]
  generate sequences of length 3 for arr = [3, 3, 2, 2, 5]
  returning [[3, 3, 2], [3, 2, 2], [2, 2, 5]]
common = []
n = 2
  generate sequences of length 2 for arr = [2, 2, 3, 3, 5]
  returning [[2, 2], [2, 3], [3, 3], [3, 5]]
  generate sequences of length 2 for arr = [3, 3, 2, 2, 5]
  returning [[3, 3], [3, 2], [2, 2], [2, 5]]
common = [[2, 2], [3, 3]]

Как common.empty? #=> false, [[2, 2], [3, 3]] возвращается.

...