найти сходство последовательностей в рубине

Question

Я хочу найти сходство двух последовательностей в Ruby, основанное исключительно на количестве общих значений.Последовательное расположение значений не должно иметь значения.Что также не должно иметь значения, так это то, имеет ли одна последовательность какие-либо значения, которых нет у другой последовательности.Мне было предложено расстояние Левенштейна, но оно вычисляет количество правок, необходимых для того, чтобы последовательности были идентичны .Вот простой пример, где есть недостаток:

[1,2,3,4,5]
[2,3,4,5,6,7,8,9]
#Lev distance is 5

[1,2,3,4,5]
[6,7,8,9,10]
#Lev distance is 5

В идеальном мире первый набор будет иметь гораздо большее сходство, чем второй набор.Грубое, очевидное решение состоит в том, чтобы использовать вложенные циклы для проверки каждого значения первой последовательности относительно каждого значения второго.Есть ли более эффективный способ?

Answer 1

Вы можете сделать пересечение для пары массивов, используя &, например:

a = [1,2,3,4,5]
b = [2,3,4,5,6,7,8,9]

common = a & b   # =>  [2, 3, 4, 5]
common.size      # =>  4

Это то, что вы ищете?

Answer 2

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

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