Вычисление самой длинной общей подпоследовательности двух списков в схеме за полиномиальное время

Question

Так что мне нужно вычислить самую длинную общую подпоследовательность из двух списков, но это должно быть за полиномиальное время. Единственная проблема, которую я имею, состоит в том, что мне не разрешено использовать "!" совсем. Это означает, что я не могу изменить значение vetcor или списка с помощью set !. Я не могу найти полиномиальный алгоритм, который не требует двухмерного списка или какого-либо массива. У кого-нибудь есть идеи?

Answer 1

Вам не нужно использовать set! (или любую другую операцию изменения), чтобы использовать 2d списки или векторы.

Вы можете использовать стандартный алгоритм динамического программирования с двухмерным вектором, но вместо изменения вектора для вставки значения, рассчитанного для данной ячейки, вы используете build-vector для создания нового вектора, который совпадает со старым один, за исключением того, что вы изменили значение в данной позиции.

Это очень неэффективно, но все еще полиномиально, и я не думаю, что это можно сделать действительно эффективно без лени или мутаций.

Редактировать: Использование build-vector для этого будет выглядеть примерно так:

(build-vector n (lambda (i)
  (build-vector n (lambda (j)
    (if (and (= i x) (= j y))
        new-value
        (vector-ref (vector-ref old-vector i) j))))))

Где old-vector - это вектор n*n, который вы хотите скопировать, и вы хотите заменить значение в позиции x,y значением new-value. (Примечание. Использование такой функции почти всегда является ошибкой в ​​реальной жизни, поскольку, как я уже сказал, это довольно неэффективно).