1

返回两个数组的数组元素的公共最长序列。序列，包括重复并位于数组中的任何位置。

例如，我想检索该子集，这是理想情况下使用最少代码量（例如使用集合操作）[2,2,3]的通用序列，arr1而不会将其转换为arr2intsstrings

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

1 回答 1

0

如果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]]返回。

于 2018-06-25T21:10:15.930 回答