Алгоритм группировки повторений в последовательности

Question

Дана последовательность чисел, например: 1, 2, 1, 2.
Существует ли какой-либо известный алгоритм для обнаружения повторений и группировки их так, чтобы результирующая последовательность имела максимально короткий размер?

Например, для предыдущей последовательности результат будет (1, 2)x2.

Больше примеров:

Input: 1, 1, 1, 2, 1, 1, 1, 2
Output: ((1)x3, 2)x2

Input: 1, 2, 1, 2, 1, 2
Output: (1, 2)x3

Input: 1, 1, 1, 2, 1, 2
Output: (1)x2, (1, 2)x2

EDIT:
Длина результата (например, (1, 2)x2) не включает дополнительную информацию, касающуюся группировки и повторения (то есть игнорируется (),x и число после x).

Например, длина (1, 2)x2 фактически равна 2. Длина ((1)x3, 2)x2 по-прежнему равна 2, поскольку мы рассматриваем только количество элементов, принадлежащих исходной последовательности (в данном случае 1 и 2).

Answer 1

Вы можете использовать метод динамического программирования. Давайте определим n как длину входной последовательности и DP[i][j] как минимально возможную длину, в которую будет сжиматься подстрока, начиная с индекса i и заканчивая индексом j. Тогда есть два случая:

• последовательно клей: DP[i][j] = min(DP[i][k] + DP[k + 1][j]) для всех k от i до j - 1;

• повторений: DP[i][j] = min(DP[i][k]) для всех таких k, которые делят подстроку i..j на идентичные длины подстрок k - i + 1. Я думаю, что минимум будет в минимально возможном значении k.

Из двух вариантов выберите минимальный. Сама строка также может быть восстановлена ​​(ее можно сохранить дополнительно, а также пересчитать). Исходные данные DP[i][i] = 1 для всех i от 1 до n. Ответ в DP[1][n] (если использовать массивы с 1 индексом).