最大化序列中数字之间的差异

Question

我需要帮助找到解决以下问题的算法的概括性想法。这个问题是我的作业。它看起来可以通过一种贪婪的方法来解决，但我找不到一个简单的解决方案。以下是问题描述：

给出一个序列 N 个数字 a_1 ... a_n，使得 0 = a_1 < a_2 < ... < a_n。你必须消除这些数字中 最多 M 个，使得任意两个相邻的数字之间的最小差值 a_i+1 - a_i 最大化。

你不可以消除第一个和最后一个元素，即 a_0 和 a_n。同时，你必须尽量少地消除数字：如果消除 M-1 个数字，你可以得到最短距离 D，并且如果再消除一个数字（共消除M个），你仍然具有相同的最小差值，你就不能消除这个最后一个数字。

我不是要求完全解决这个问题。只是需要一些指导，告诉我算法可能是什么样子。

编辑：一些测试样例。请记住，可能有多个有效的解决方案。

Remove at most 7 from:
0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100

Solution:
0 7 15 26 31 38 44 53 60 73 80 88 93 100

Remove at most 8 from:
0 3 7 10 15 26 38 44 53 61 76 80 88 93 100

Solution:
0 15 38 53 76 88 100

- pulagroasa

---

反思之后，ElKamina的答案不仅正确而且非常类似于我的！我之前批评它的评论是错误的；我现在已经删除了它。 - j_random_hacker

Answer 1

[编辑：我起初声称ElKamina的答案是错误的，但我现在已经自己确信它不仅正确，而且几乎与我的（后来的）答案相同: -P 对于我来说仍然有点简略！]

这是一个精确的O(NM^2)-时间、O(NM)-空间动态规划算法，可以在毫秒级别内得出所有OP示例的正确答案。基本思想是:

1. 每当我们强加一个特定数字不应该被删除的约束时，它会在两个子问题之间形成一个“栅栏”，以这样的方式解决每个子问题最优地保证了满足该约束下的总体问题的最优解。
2. 每个最优解必须以一个未被删除的数字开头，然后是一些连续删除的数字，接着是一个未被删除的数字，然后是从第二个未被删除的数字开始并使用适当减少的M的其余问题的最优解。

下面，x[i]表示列表中的第i个数字，索引从0开始。

递归

设f(i，j)为从位置0 <= i < N开始的数字列表的后缀中保留此(i.e.第i个)数字并删除恰好j个之后可以获得的最佳(最大的最小)间隔大小。以下递归显示了如何计算这个值：

f(i, j) = max(g(i, j, d)) over all 0 <= d <= min(j, N-i-2)
g(i, j, d) = min(x[i+d+1] - x[i], f(i+d+1, j-d))

为防止删除“超出末尾”的元素，min(j, N-i-2)代替了普通的j。我们只需要以下两个基本情况：

f(N-1, 0) = infinity (this has the effect of making min(f(N-1), 0), z) = z)
f(N-1, j > 0) = 0 (this case only arises if M > N - 2)

工作原理

更详细地说，为了计算f(i,j)，我们要循环所有可能的连续删除数（包括零），从位置i+1开始，在每种情况下计算以下两个值中的最小值：(a)由这段删除块形成的间隔和(b)在此块右侧第一个未删除数字上开始的子问题的最佳解。 重要的是要指定块中的第一个数字(x[i])没有被删除，以便前一个(父)子问题的间隔总是“封顶”的。 这是一个棘手的部分，我花了一些时间才想明白。

使其快速

如果您编写上述普通递归代码，它将有效，但时间复杂度将呈指数级增长。通过记忆化f()，我们保证其主体最多只运行N*M次(每个不同的参数组合运行一次)。每次函数运行时，它执行O(M)的工作，扫描越来越长的删除块，总共需要O(NM^2)的时间。

您不能使用更少的删除创建更大的间隔，因此可以通过查看M+1个结果f(0, M)，f(0, M-1)，...，f(0, 0)来找到总体最大的最小间隔大小，以查找小于先前数字的第一个数字：该先前数字是答案，而传递给f()的第二个参数是所需的最小删除数。要找到最佳解（即特定数字的列表），可以在单独的前任数组中记录所做的决策，以便p[i,j]给出导致f(i,j)的最佳解的d的值（可以将其转换为i和j的先前值）。 （也许“前任”在这里是令人困惑的：它指的是在当前子问题之前解决的子问题，尽管这些子问题出现在表示当前子问题的后缀“之后”（右侧）。）然后可以跟随这些链接以恢复删除/不删除所做的决策。

C++代码示例

http://ideone.com/PKfhDv

补充说明：早期失误

对于像这样棘手的问题，查看错误方法并确定它们的错误之处可能会有所帮助...... :-/ 我认为我已经解决了这个问题，但我没有注意到需要返回使用尽可能少的删除的解决方案的要求，而我最初修复这个问题的尝试没有成功。

起初，我尝试定义f(i, j)为从位置0 <= i < N开始的数字列表后缀中保留这个数（即第i个数字）并删除任意多个后续数字（不一定是连续的），可以获得的最优（最大最小）区间大小。但这引起了一个微妙的问题：不能保证可以通过子问题的最优解来组装出这个问题的最优解。我最初认为可以通过将函数更改为返回一个（区间大小，实现该区间大小所需的最小删除数）对而不仅仅是一个区间大小，并在共享最大最小区间大小的操作之间选择始终最小化删除次数的操作，从而修复这个问题。但一般来说这不是正确的，因为子问题（即数字列表的某个后缀）的最优解会花费删除来使该区域的最小区间尺寸尽可能大，即使这些删除最终被浪费，因为全面解决方案的前缀将强制整体最小值更低。这里有一个反例，使用返回（区间大小，实现该大小所需的最小删除数）对的f()：

Problem: M = 1, X = [10 15 50 55].

f(2, 0) = (5, 0) (leaving [50 55])
f(1, 1) = (40, 1) (delete 50 to leave [15 55]); *locally* this appears better
          than not deleting anything, which would leave [15 50 55] and yield
          a min-gap of 5, even though the latter would be a better choice for
          the overall problem)
f(0, 1) = max(min(5, f(1, 1)), min(40, f(2, 0))
        = max(min(5, 40), min(40, 5))
        = (5, 1) (leaving either [10 15 55] or [10 50 55])

我没有展示f(0,1)返回的二元组中第二个元素的计算过程，因为这很难简洁地表达出来，但显然它将是1，因为尝试的两种选择都需要删除一个字符。

- j_random_hacker

---

哇，写得非常好，示例代码也很棒。我会投票支持你的答案成为被接受的答案，但现在已经被接受的答案不能删除了。 - Scott Mermelstein

很好。不过，我可能需要相当长的时间才能理解它。 - גלעד ברקן

Answer 2

使用动态规划。

线索X（i，j）包含了前i个元素中选择的最小距离，其中有j个被选中（即未删除）。

这将为您提供精确的解决方案。复杂度= O(MN ^ 2)，因为对于每个i值，只有M个有效的j值，并且每次调用函数需要执行O（M）工作。

让元素为A1，A2，...，An

更新公式为：

X（i + 1，j + 1）= Max（Min（A（i + 1）-Ak，Xkj）for k <= i）

[由j_random_hacker编辑以添加评论中的信息]

- ElKamina

---

我知道OP只是在寻求一些方向，但您能否详细说明一下？我想更多地了解这个解决方案。 - AndyG

@SauceMaster 我已经在答案中添加了实际的更新。如果你需要更多帮助，请告诉我。本质上，如果你已经解决了所有子字符串0:1、0:2、...、0:i的问题，那么你可以重复使用这些信息来计算0:(i+1)的解决方案。 - ElKamina

@j_random_hacker，你的第一个观察是错误的。因为我跟踪的是“已选择”而不是“已删除”的数字，所以我没问题。不过你对第二个观察是正确的，复杂度确实是O(N^3)。 - ElKamina

@j_random_hacker 既然你已经有了一个几乎相同的答案，我认为我的回答也没有用处。不过我仍然认为这个答案是比较完整的（在SO上，我大多数时候只提供方向，而不是确切的答案）。无论如何，我很高兴能够说服你我的答案是有效的。祝你有愉快的一天！ - ElKamina

好的，我已经自己修复了时间复杂度（反正为了点赞也需要编辑！） - j_random_hacker

Answer 3

我原本不想使用全组合方法，但经过多次尝试，似乎这是与j_random_hacker的结果匹配的唯一方法。（以下某些评论与此答案的早期版本有关。）我对j_random_hacker/ElKamina在Haskell中表达算法（'jrhMaxDiff'）的简洁印象深刻。他的函数'compareAllCombos'查找我们两种方法的结果差异：

*Main> compareAllCombos 7 4 4
Nothing

算法如下：

1. Group the differences: [0, 6, 11, 13, 22] => [[6],[5],[2],[9]]

2. While enough removals remain to increase the minimum difference, extend the 
   minimum difference to join adjacent groups in all possible ways:

   [[6],[5],[2],[9]] => [[6],[5,2],[9]] and [[6],[5],[2,9]]...etc.

   Choose the highest minimum difference and lowest number of removals.

Haskell 代码：

import Data.List (minimumBy, maximumBy, groupBy, find)
import Data.Maybe (fromJust)

extendr ind xs = 
  let splitxs = splitAt ind xs
      (y:ys) = snd splitxs
      left = snd y
      right = snd (head ys)
  in fst splitxs ++ [(sum (left ++ right), left ++ right)] ++ tail ys

extendl ind xs = 
  let splitxs = splitAt ind xs
      (y:ys) = snd splitxs
      right = snd y
      left = snd (last $ fst splitxs)
  in init (fst splitxs) ++ [(sum (left ++ right), left ++ right)] ++ tail (snd splitxs)

extend' m xs =
  let results = map (\x -> (fst . minimumBy (\a b -> compare (fst a) (fst b)) $ x, x)) (solve xs)
      maxMinDiff = fst . maximumBy (\a b -> compare (fst a) (fst b)) $ results
      resultsFiltered = filter ((==maxMinDiff) . fst) results
  in minimumBy (\a b -> compare (sum (map (\x -> length (snd x) - 1) (snd a))) (sum (map (\x -> length (snd x) - 1) (snd b)))) resultsFiltered
   where 
     solve ys = 
       let removalCount = sum (map (\x -> length (snd x) - 1) ys)
           lowestElem = minimumBy (\a b -> compare (fst a) (fst b)) ys
           lowestSum = fst lowestElem
           lowestSumGrouped = 
             map (\x -> if (fst . head $ x) == 0 
                           then length x 
                           else if null (drop 1 x) 
                                   then 1 
                                   else if odd (length x)
                                           then div (length x + 1) 2
                                           else div (length x) 2)
             $ filter ((==lowestSum) . fst . head) (groupBy (\a b -> (fst a) == (fst b)) ys)
           nextIndices = map snd . filter ((==lowestSum) . fst . fst) $ zip ys [0..]
           lastInd = length ys - 1
       in if sum lowestSumGrouped > m - removalCount || null (drop 1 ys)
             then [ys]
             else do
               nextInd <- nextIndices          
               if nextInd == 0
                  then solve (extendl (nextInd + 1) ys)
                  else if nextInd == lastInd
                          then solve (extendr (nextInd - 1) ys)
                          else do 
                            a <- [extendl nextInd ys, extendr nextInd ys]
                            solve a

pureMaxDiff m xs = 
  let differences = map (:[]) $ tail $ zipWith (-) xs ([0] ++ init xs)
      differencesSummed = zip (map sum differences) differences
      result = extend' m differencesSummed
      lowestSum = fst result
      removalCount = sum (map (\x -> length (snd x) - 1) (snd result))
  in if null (filter ((/=0) . fst) differencesSummed)
        then (0,0)
        else (removalCount, lowestSum)

-- __j_random_hacker's stuff begins here

-- My algorithm from https://dev59.com/Rm_Xa4cB1Zd3GeqP3qxX#15478409.
-- Oddly it seems to be much faster when I *don't* try to use memoisation!
-- (I don't really understand how memoisation in Haskell works yet...)
jrhMaxDiff m xs = fst $ fromJust $ find (\(x, y) -> snd x > snd y) resultPairsDesc
  where
    inf = 1000000
    n = length xs
    f i j =
      if i == n - 1
         then if j == 0
                 then inf
                 else 0
         else maximum [g i j d | d <- [0 .. min j (n - i - 2)]]
    g i j d = min ((xs !! (i + d + 1)) - (xs !! i)) (f (i + d + 1) (j - d))
    resultsDesc = map (\i -> (i, f 0 i)) $ reverse [0 .. m]
    resultPairsDesc = zip resultsDesc (concat [(tail resultsDesc), [(-1, -1)]])

-- All following code is for looking for different results between my and groovy's algorithms.
-- Generate a list of all length-n lists containing numbers in the range 0 - d.
upto 0 _ = [[]]
upto n d = concat $ map (\x -> (map (\y -> (x : y)) (upto (n - 1) d))) [0 .. d]

-- Generate a list of all length-maxN or shorter lists containing numbers in the range 0 - maxD.
generateAllDiffCombos 1 maxD = [[x] | x <- [0 .. maxD]]
generateAllDiffCombos maxN maxD =
  (generateAllDiffCombos (maxN - 1) maxD) ++ (upto maxN maxD)

diffsToNums xs = scanl (+) 0 xs

generateAllCombos maxN maxD = map diffsToNums $ generateAllDiffCombos maxN maxD

-- generateAllCombos causes pureMaxDiff to produce an error with (1, [0, 0]) and (1, [0, 0, 0]) among others,
-- so filter these out to look for more "interesting" differences.
--generateMostCombos maxN maxD = filter (\x -> length x /= 2) $ generateAllCombos maxN maxD
generateMostCombos maxN maxD = filter (\x -> length x > 4) $ generateAllCombos maxN maxD

-- Try running both algorithms on every list of length up to maxN having gaps of
-- size up to maxD, allowing up to maxDel deletions (this is the M parameter).
compareAllCombos maxN maxD maxDel =
  find (\(x, maxDel, jrh, grv) -> jrh /= grv) $ map (\x -> (x, maxDel, jrhMaxDiff maxDel x, pureMaxDiff maxDel x)) $ generateMostCombos maxN maxD
--  show $ map (\x -> (x, jrhMaxDiff maxDel x, pureMaxDiff maxDel x)) $ generateMostCombos maxN maxD

- גלעד ברקן

---

看起来不错。但是我经常被证明是错误的，所以反例专家肯定会有办法证明相反的。 - Scott Mermelstein

@ScottMermelstein 谢谢您的关注，期待反例，保持信心。 - גלעד ברקן

终于，我尝试将我的算法翻译成Haskell，并添加了一些自动化测试工具：http://ideone.com/sTmqUO。首先，你的`maxDiff`函数在X=[0, 0]或X=[0, 0, 0]且M=1时会出现“Exception: Prelude.head: empty list”的错误。经过筛选测试数据，我发现compareAllCombos 5 2 2可以产生Just ([0,0,0,0,0],(0,0),(1,0))--也就是说，你的算法错误地报告M=1，X=[0, 0, 0, 0, 0]需要删除1个元素。希望这段代码对你有用！ - j_random_hacker

很抱歉，我不能再花更多时间在这上面了，但你应该能够使用我的compareAllCombos函数自行检查反例。如果你将任何参数增加得太多，它会花费很长时间！ - j_random_hacker

@j_random_hacker，你说得对。我现在明白了其中的区别。我的算法对很多例子都不起作用。也许我需要再好好想一想。你的比较函数非常有帮助。也许它会激励我去学习动态解决方案的工作原理。 - גלעד ברקן

Answer 4

我想我找到了解决方案。它在两个样本集上有效，至少如此。它不一定返回与答案相同的集合，但是返回的集合具有相同的最小值。它是迭代和贪婪的，这很好，而且有很多优化方法。看起来它的时间复杂度是MLog(N)。

重要的是要意识到数字并不重要 - 只有它们之间的差异才重要。当你“删除一个数字”时，实际上只是将两个相邻的差异合并在一起。我的算法将关注这些差异。回到导致这些差异的项目并随着进程删除是一件简单的事情。

算法

1. 创建一个有序列表/数组，列出每个数字之间的差异。
2. 找到最小差异 x。如果 x 的计数 > 剩余的 M，则停止。您已经处于最佳情况。
3. 对于从最左边开始的每个 x 值，将该差异与较低的相邻值组合（并删除该 x）。如果相邻值相等，则您的决定是任意的。如果只有一个相邻值的值为 x，则与另一个相邻值组合。（如果没有选择，例如 [1, 1, ...]，则与匹配的 X 组合，但如果可以避免则避免。）
4. 回到步骤 2，直到用完 M。

算法说明

第三步有一个我标记为任意决定的点。它可能不应该是这样，但你已经涉及到足够复杂的情况，这是一个关于你想要添加多少复杂性的问题。这种武断性是允许存在多个不同正确答案的原因。如果你看到两个相邻的数值相同，在这一点上，我会随意选择一个。理想情况下，你应该检查相距2、3等的邻居对，并倾向于较低的那个。如果你在扩展时遇到边缘，我不确定该怎么办。最终，为了完美地完成这一部分，你可能需要递归调用这个函数，并看哪个评估更好。

走过样本数据:

先看第二个:

从以下数字中删除至多8个: 0 3 7 10 15 26 38 44 53 61 76 80 88 93 100

[3, 4, 3, 5, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 8

删除3. 边缘上的移除只能朝一个方向添加:

[7, 3, 5, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 7

[7, 8, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 6

接下来，移除4：[7, 8, 11, 12, 6, 9, 8, 15, 12, 5, 7] M = 5

接下来，移除5：[7, 8, 11, 12, 6, 9, 8, 15, 12, 12] M = 4

接下来，移除6：[7, 8, 11, 12, 15, 8, 15, 12, 12] M = 3

接下来，移除7：[15, 11, 12, 15, 8, 15, 12, 12] M = 2

接下来，删除8：[15, 11, 12, 15, 23, 12, 12] M = 1 // 注意，添加方向是任意决定的

最后，删除11：[15, 23, 15, 23, 12, 12]

请注意，在答案中，最小差为12。

先处理第一个

从以下数据中最多删除7个：

0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100

[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 7, 1, 12, 3, 4, 1, 7, 5, 7] M = 7

删除1：

[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 4, 1, 7, 5, 7] M = 6

[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 5

还剩下4个3，所以我们可以将它们移除：

[7, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 4

[7, 8, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 3

[7, 8, 11, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 2 // 注意任意添加到右侧

[7, 8, 11, 5, 7, 6, 9, 8, 12, 8, 5, 7, 5, 7] M = 1

我们接下来会移除5，但是只允许移除1个，而我们只有3个，所以我们就停在这里。我们的最小差值为5，与解决方案相匹配。

注意：从SauceMaster提出的1、29、30、31、59情况中，编辑了将相同的X值组合在一起的想法，以避免这样做。

- Scott Mermelstein

---

好的回答，它帮助我理解了我的算法是如何失败的。 - גלעד ברקן

即使没有出现“任意”选择，这个算法也可能是错误的：例如，在M=2时，它无法处理序列0 6 11 13 22。作为差异，它们是6 5 2 9，因此您的算法首先会将5和2组合成6 7 9，然后将6和7组合成13 9。但更好的方法是先将2和9组合成6 5 11，然后将6和5组合成11 11。 - j_random_hacker

其次，复杂度不能是O(Mlog N) -- 因为你必须读取所有N个数字，所以至少有一个N的因素在其中！ - j_random_hacker

我不能反驳你提供的测试用例，但是我已经没有更好的想法了。也许@pulagroasa可以发布他的算法，因为他找到了一个他满意的算法。 - Scott Mermelstein

事实证明，我抱怨ElKamina的DP算法是错误的——它基本上是正确的，而且基本上与我的算法相同，只是“方向”相反，并计算未删除的数字而不是已删除的数字。（它只是比最初宣传的慢和晦涩！）它们都会每次找到正确的答案。附：如果您在评论中写入“@j_random_hacker”，我将收到通知，否则不会。 - j_random_hacker

@ScottMermelstein 你好，我又发布了一个简单的答案来完善你的算法，如果你感兴趣可以看一下。https://dev59.com/Rm_Xa4cB1Zd3GeqP3qxX#15560133 - גלעד ברקן