包含所有数字的最小子列表

Question

我正在尝试用 sml 编写一个程序，它接收列表的长度、将出现在列表中的最大数量，当然还有列表。然后计算包含所有数字的最小 "sub-list" 的长度。

我尝试使用滑动 window 方法，有两个索引，前和尾。前端首先扫描，当它找到一个数字时，它会将它已经看到这个数字的次数写入地图。如果程序找到所有数字，则调用尾部。尾部扫描列表，如果它发现一个数字被看到的次数超过 1 次，它就会将其删除。

到目前为止我尝试过的代码如下：

structure Key=
 struct
  type ord_key=int
  val compare=Int.compare
 end


fun min x y = if x>y then y else x;


structure mymap = BinaryMapFn ( Key  );

fun smallest_sub(n,t,listall,map)=
let
 val k=0
 val front=0
 val tail=0

 val minimum= n; 

 val list1=listall;
 val list2=listall;

 fun increase(list1,front,k,ourmap)=
  let 
   val number= hd list1
   val elem=mymap.find(ourmap,number)
   val per=getOpt(elem,0)+1

   fun decrease(list2,tail,k,ourmap,minimum)=
    let 
     val number=hd list2
     val elem=mymap.find(ourmap,number)
     val per=getOpt(elem,0)-1
     val per1=getOpt(elem,0)
    in
     if k>t then
      if (per1=1) then decrease(tl list2,tail+1,k-1,mymap.insert(ourmap,number,per),min minimum (front-tail))
      else decrease(tl list2,tail+1,k,mymap.insert(ourmap,number,per),min minimum (front-tail))
     else increase (list1, front,k,ourmap)
    end

  in
   if t>k then
    if (elem<>NONE) then increase (tl list1,front+1,k,mymap.insert(ourmap,number,per))
    else increase(tl list1,front+1,k+1,mymap.insert(ourmap,number,per))
   else (if (n>front) then decrease(list2,tail,k,ourmap,minimum) else minimum)
  end


in
  increase(list1,front,k,map)
end


fun solve (n,t,acc)= smallest_sub(n,t,acc,mymap.empty)

但是当我用这个调用它时 smallest_sub(10,3,[1,3,1,3,1,3,3,2,2,1]);这是行不通的。我做错了什么？？

示例：如果输入是 1,3,1,3,1,3,3,2,2,1 程序应该识别包含所有数字且最小的列表部分是 1， 3,3,2 和 3,2,2,1 所以输出应该是 4

Answer 1

这个 "smallest sub-list that contains all values" 的问题似乎在没有成功答案的新问题。这是因为它不是最小的，完整且可验证的示例.

因为你使用了"sliding window"方法，索引前面和后面根据您的输入，需要 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，前面有int参数表示 map 的值类型，是 count 这个值的次数发生值。

在下面构建 initialCountMap 时，您使用 CountMap.increment，并且当您使用 "sliding window" 方法时，您使用 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 中的元素数可能有找到它的功能。

包含所有数字的最小子列表

Smallest sub-list that contains all numbers

sml

smlnj