По заданным последовательностям S и T найдите последовательности X и Y такие, что S и T принадлежат к перемешиванию X и Y. (X и Y могут не существовать)

Question

Мне нужно создать динамический c программный алгоритм, который решит эту проблему: для заданных последовательностей S и T найдите последовательность X и Y так, чтобы S и T принадлежали тасованию X и Y.

Последовательности S и T даны с длиной n. Мы хотим найти последовательность X и последовательность Y, каждая из которых имеет длину k an l, такую, что S и T принадлежат случайному произведению X и Y. Зная, что (k + l = n)

Как I go о решении этой проблемы с использованием динамического программирования c. Мне интересно знать, какой может быть политика использования прошлых результатов. На данный момент я понятия не имею.

Может ли кто-нибудь сделать пример с S = GTACA и T = AGCAT? Предположим, что моя таблица выглядит так:

Мы хотим, чтобы зеленая ячейка предоставляла последовательности X и Y или ничего не предоставляла (В случае, если X и Y не существует)

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

ОБНОВЛЕНИЕ

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

Моя таблица программирования Dynami c выглядит следующим образом:

Если я допустил ошибку, скажите, пожалуйста, где я могу ее исправить.

Answer 1

Кажется, это Самая длинная общая проблема подпоследовательности в скрытом виде: При заданных S и T вы найдете самую длинную общую подпоследовательность. Это было бы X. Упущенные элементы были бы последовательностью Y, если они появляются в том же порядке в S и T, или они указывают, что такие X и Y не существуют, если они не появляются в одном и том же порядке.

В вашем примере самая длинная общая подпоследовательность - ACA. Следовательно, X = ACA и пропущенные элементы в S и T равны GT, появляясь в одном и том же порядке в обоих. Следовательно, Y = GT.

РЕДАКТИРОВАТЬ: Ваша динамическая таблица программирования c неверна. Например, в 3-й строке и 4-м столбце ячейка должна иметь две последовательности A и G, а не одну последовательность AG. Цитата из Википедии:

Если они не равны, то длинная из двух последовательностей [...] сохраняется. (Если они имеют одинаковую длину, но не идентичны, то оба они сохраняются.)

Вот полная таблица (без пустых последовательностей):

  | G   T    A       C             A
-------------------------------------------
A |          A       A             A
G | G   G    A,G     A,G           A,G 
C | G   G    A,G     AC,GC         AC,GC
A | G   G    GA      AC,GA,GC      ACA,GCA
T | G   GT   GA,GT   AC,GA,GC,GT   ACA,GCA

Это дает нам два решения для X, но только одно из них дает нам действительное Y:

• Если X = ACA, то Y = GT на основе как S, так и T - действительное решение.
• Если X = GCA, то Y = TA на основе S, но AT на основе T - так что это не решение.

Я признаю, что ответ выше не является полным решением проблемы. Из рассуждений, которые я привел в своем комментарии ниже, следует, что X или Y являются подпоследовательностями LCS. Какова подпоследовательность, которую еще нужно как-то определить.