Эта проблема "наименьшего подсписка, который содержит все значения", кажется, повторяется в новых вопросах без успешного ответа.Это потому, что это не минимальный, полный и проверяемый пример .
Поскольку вы используете подход с «скользящим окном», индексируя переднюю и заднюю часть вашегона вход, список, требующий O (n) времени для индексации элементов, не идеален.Вы действительно хотите использовать массивы здесь.Если ваша функция ввода должна иметь список, вы можете преобразовать его в массив для целей алгоритма.
Я бы хотел выполнить очистку кода перед ответом, потому что текущий код выполняется вручнуюэто немного сложно, потому что это так сжато.Вот пример того, как вы можете абстрагироваться от учета того, содержит ли данный подсписок хотя бы одну копию каждого элемента в исходном списке:
Редактировать: Я изменилкод ниже после первоначальной публикации.
structure CountMap = struct
structure IntMap = BinaryMapFn(struct
type ord_key = int
val compare = Int.compare
end)
fun count (m, x) =
Option.getOpt (IntMap.find (m, x), 0)
fun increment (m, x) =
IntMap.insert (m, x, count (m, x) + 1)
fun decrement (m, x) =
let val c' = count (m, x)
in if c' <= 1
then NONE
else SOME (IntMap.insert (m, x, c' - 1))
end
fun flip f (x, y) = f (y, x)
val fromList = List.foldl (flip increment) IntMap.empty
end
То есть CountMap - это int IntMap.map, где Int представляет фиксированный тип ключа карты, равный int, а *Параметр 1022 * перед ним представляет тип значения карты, представляющий собой count от того, сколько раз это значение имело место.
При построении initialCountMap ниже вы используете CountMap.increment и когда вы используете подход «скользящего окна», вы используете CountMap.decrement для создания нового countMap, который вы можете проверить рекурсивно.
Если вы уменьшаете вхождение ниже 1, вы ищетев подсписке, который не содержит каждый элемент хотя бы один раз;мы исключаем любое решение, позволяя CountMap.decrement return NONE.
. Когда все это оборудование абстрагировано, сам алгоритм становится намного проще выразить.Во-первых, я хотел бы преобразовать список в массив, чтобы индексирование стало O (1) , потому что мы будем много индексировать.
fun smallest_sublist_length [] = 0
| smallest_sublist_length (xs : int list) =
let val arr = Array.fromList xs
val initialCountMap = CountMap.fromList xs
fun go countMap i j =
let val xi = Array.sub (arr, i)
val xj = Array.sub (arr, j)
val decrementLeft = CountMap.decrement (countMap, xi)
val decrementRight = CountMap.decrement (countMap, xj)
in
case (decrementLeft, decrementRight) of
(SOME leftCountMap, SOME rightCountMap) =>
Int.min (
go leftCountMap (i+1) j,
go rightCountMap i (j-1)
)
| (SOME leftCountMap, NONE) => go leftCountMap (i+1) j
| (NONE, SOME rightCountMap) => go rightCountMap i (j-1)
| (NONE, NONE) => j - i + 1
end
in
go initialCountMap 0 (Array.length arr - 1)
end
Это выглядитчтобы работать, но ...
Выполнение Int.min (go left..., go right...) влечет за собой стоимость O (n ^ 2) стековой памяти (в случае, когда вы не можете исключить ни того, ни другого оптимального).Это хороший вариант использования для динамического программирования, потому что ваши рекурсивные подзадачи имеют общую подструктуру, то есть
go initialCountMap 0 10
|- go leftCountMap 1 10
| |- ...
| `- go rightCountMap 1 9 <-.
`- go rightCountMap 0 9 | possibly same sub-problem!
|- go leftCountMap 1 9 <-'
`- ...
Так что, возможно, есть способ сохранить рекурсивную подзадачу в массиве памяти ине выполнять рекурсивный поиск, если вы знаете результат этой подзадачи.Как сделать запоминание в SML - хороший вопрос сам по себе.Как сделать чисто функциональное запоминание на не ленивом языке, еще лучше.
Еще одна оптимизация, которую вы можете сделать, это то, что если вы когда-нибудь найдете подсписок размером с число уникальных элементов, вам нужносмотреть не дальше.Это число случайно является количеством элементов в initialCountMap, и IntMap, вероятно, имеет функцию для его поиска.