Разница в массиве как серия действий

Question

Вкратце: у меня есть два массива, которые могут быть разными, и я хотел бы получить разницу/преобразование как серию «действий» (добавляет и удаляет). То есть, в основном примере:

Current: [a, b, d] 
Desired: [a, b, c, d] 
Actions: Add c in position 2 

В основном, инструкция, как преобразовать текущий массив, так что у него есть одни и те же элементы и порядок в качестве необходимого массива. Для моего приложения каждое изменение запускает события, которые обновляют пользовательский интерфейс и т. Д., Поэтому было бы очень предпочтительным, если бы действия не были «избыточными»: то есть вышеописанное могло быть remove d, add c @ 2, add d @ 3, но это может вызвать много нежелательной обработки в другом месте в системе.

Возможно, в качестве еще одного примера, который мог бы помочь проиллюстрировать:

Current: [a, b, d] 
Desired: [b, c, d, a] 
Actions: remove a, add c @ 1, add a @ 3 

Я полагаю, что это то, что было решено раньше, но это своего рода трудно найти его, так как «разность массива» не дает правильные результаты.

Если это имеет значение, я реализую это в Javascript, но, я думаю, алгоритм является агностиком языка.

Answer 1

Это действительно существует, это называется edit distance. Основной алгоритм не запоминает вид редактирования, но его легко модифицировать.

Один вид расстояния редактирования - Levenshtein distance. Эта страница wikipedia содержит некоторые фрагменты кода, которые могут оказаться полезными.

Hirschberg's algorithm также может быть полезным.