javascript - 确定在删除和后续更改包含数组后恢复元素的位置

Question

我有一个元素数组。删除了一些元素。然后以某种方式更改数组，这可以是删除或添加元素，在数组中移动元素或这些的组合。

现在我想把移除的元素放回去，让它尽可能靠近它的原始邻居。想象这些元素是文本中的句子，并且用户可以选择撤消他们刚刚删除的句子的删除。（这不是实际用例，而是等价的）

我的想法是在删除元素时保存元素 ID 列表（每个元素都有一个 uuid），然后以某种方式使用它来将元素恢复到其与数组上下文相关的原始位置。仅查看前一个元素是行不通的，因为如果在此期间删除或移动了前一个元素，它会搞砸。

查看被移除元素周围元素的平均移动似乎也不是一个好主意，因为这会导致它位于它们之间的某个随机位置，而不是在一个特别重要的位置。

编辑：显然这对我所说的“最佳”的意思不够清楚，这里有一些例子来说明我的意思：

//start
[1, 2, 3, 4, 5, 6]

//removal of 4
[1, 2, 3, 5, 6]

//array changed in some way...
[1, 2, 6, 5, 7, 8]

//should yield:
[1, 2, 4, 6, 5, 7, 8]

//more examples: (changed array, array with element added back)
[1, 2, 3, 5, 6], [1, 2, 3, 4, 5, 6]
[1, 2, 5, 6], [1, 2, 4, 5, 6]
[5, 6], [4, 5, 6]
[6, 5], [4, 6, 5]
[6, 5, 3, 2, 1], [6, 5, 4, 3, 2, 1]
[5, 6, 1, 2, 3], [5, 6, 1, 2, 3, 4]

标签： javascriptarraysalgorithmmerge

Answer 1

假设您有一个元素列表和一个目标元素。对于每个元素，我们可以计算到目标元素的偏移量（前任有-1，后继有+1等等）。如果我们愿意，我们可以将其限制在当地社区。

现在我们有一个修改后的列表，其中目标元素不存在，而其他元素的顺序不同（或消失）。但我们仍然知道偏移量。因此，每个元素都可以投票选出目标元素的新位置。如果所有选票都同意，我们就很好。但这一般不会发生。所以，我们能做些什么。

本质上，这是一个最小化问题，我们希望为目标元素选择一个新位置，以便我们最小化一些错误。我们可以非常不同地测量误差。我们希望新位置接近所有选票，因此某种形式的求和差异似乎是有意义的。

您使用平均投票位置的建议等于最小化 L2 差异误差。正如您所发现的，这对异常值非常敏感（即移动很远的单个元素）。

更稳健的选择是 L1 最小化。解决方案是投票位置的中位数。但类似的效果仍然可能发生。但是你可能还是想尝试一下。

我会主张 L0 最小化。即，采取大多数其他元素都同意的位置（计算每个位置有多少元素投票并选择最大值）。如果有多个这样的位置，则可以考虑 L1 和 L2 误差。