Наименьший подсписок, содержащий все числа

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

Поскольку вы используете подход «скользящего окна», индексируя переднюю часть а также задней вашего ввода, список, требующий На) времени для индексации элементов, не идеален. Ты действительно хочу использовать массивы здесь. Если ваша функция ввода должна иметь список, вы может преобразовать его в массив для целей алгоритма.

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

Редактировать: Я изменил приведенный ниже код после его публикации.

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, и параметр int перед ним представляет тип значения карты, будучи считать того, сколько раз это произошло значение.

При построении initialCountMap ниже вы используете CountMap.increment и когда вы используете подход «скользящего окна», вы используете CountMap.decrement для создайте новый countMap, который вы можете рекурсивно протестировать.

Если вы уменьшите вхождение ниже 1, вы просматриваете подсписок, который не содержит каждый элемент хотя бы один раз; мы исключаем любое решение позволить CountMap.decrement вернуться NONE.

Когда весь этот механизм абстрагирован, сам алгоритм становится намного сложнее. проще выразить. Во-первых, я хотел бы преобразовать список в массив, чтобы indexing становится О(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...) требует затрат в стеке О (п ^ 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 вероятно, есть функция для его поиска.