仅使用推送和删除操作将列表从顺序 A 修改为顺序 B

Question

是否有任何众所周知的算法（或明显的解决方案）仅使用 push 和 remove 操作将列表从顺序 A 转换为顺序 B？例如，从 abc d 到 bca d 可以使用以下操作完成：

remove(a)
remove(d)
push(a)
push(d)

或者，从 cb a 到 a b 将是

remove(c)
remove(b)
push(b)

或者，从 ac b 到 acb d 将是

push(d)

这里，push 将一个元素追加到列表末尾，并且 < code>remove 删除元素并移动后续元素，使列表始终处于连续状态（没有“空槽”）。此外，还有一个条件是，在任何给定时刻，列表中的相同元素只能包含一次。因此，首先在一组中执行所有remove，然后再执行所有push，这似乎是合理的。显然，remove 的顺序并不重要，但 push 的顺序却很重要。

一个简单的解决方案是首先删除所有元素，然后按所需的顺序推送所需的元素。但由于我知道大多数时候转换会非常小，相当于单个 pushes 或 removes，所以我想“重用”任何现有的正确顺序列表（例如，将 abcdef 转换为 abcde 只需要一次 remove 操作 - 与替代方案（6+5 操作）有很大不同）。那么，如何得出正确的（最小）remove 集合和push 列表呢？

Answer 1

据我所知，你将从任何地方移开并推到后面。

由于无法插入到列表的中间，因此最小化操作次数的唯一方法是线性遍历列表并删除任何不正确的元素。

即1、2、3、4、5、6、7、8、9、10→ 2, 4, 6, 7, 8, 13, 14

1. 比较 1
   1. 删除 1
2. 比较 2
3. 比较 3
   1. 删除 3
4. 比较 4
5. 比较 5
   1. 删除 5
6. 比较 6
7. 比较 7
8. 比较 8
9. 比较 9
   1. 删除 9
10. 比较 10
    1. 删除 10 个
       （已结束）
11. Push 13
12. Push 14

如果你的推送没有那么有限，会有更有效的方法来做到这一点。

Answer 2

这并不是“众所周知”，而是我刚刚想到的。

1. 删除原始列表中不存在的所有元素；将每个删除操作添加到操作列表中。
2. 添加工作中缺少的任何元素；将每个添加操作添加到操作列表中。
3. 为原始列表的每个元素分配一个“顺序号”，这是其类似物在所需列表中的位置。 （参见下面的代码片段。）
4. 找到第一个元素（0位于原始1< /a>）以及从那里开始的最后一个元素（1位于原始 2）。
5. 删除此范围之外位置的所有元素并将它们放入其他临时列表中；将每个删除操作添加到操作列表中。
6. 根据“订单号”对临时列表进行排序。
7. 从临时列表中按顺序添加元素；将每个添加操作添加到操作列表中。
8. 验证这个新转换的列表是否与所需的列表匹配。
9. 返回操作列表。

例如。从第 2 步开始：

2013年1234

abcd bcad

因为您只能添加和删除——不能插入元素或添加/删除范围——我认为您不能保留任何有序子段的现有顺序 除了 0 中的有序段之外。这就是在步骤 4 中删除所有其他元素的原因。由于您不必在删除后立即添加这些元素（根据您的示例），我认为可以将它们存放在某个地方。那么，为什么不将它们存储在可排序列表中并根据分配的“订单号”进行排序以确定添加的顺序呢？

除非我误解了你的问题，否则你对添加/删除操作的顺序感兴趣，所以你不关心实际转换列表（因为你已经有了转换后的列表）；您想要创建转换列表的步骤。因此，每次在算法中添加或删除时，请将“操作”添加到操作列表（队列）中（例如 operations.Add("remove(a)")）。然后算法返回该操作列表。

我用 C# 编写了一个可能的实现。我对其进行了一些测试（下面的屏幕截图），它似乎有效。然而，它也可能不是某人可以编写的最佳实现。

public static IEnumerable<string> DetermineTransformOrder<T>(
    IEnumerable<T> original, IEnumerable<T> desired)
{
    // handle the easy case immediately
    if (original.SequenceEqual(desired))
    {
        return new List<string>();
    }

    List<KeyValuePair<int,T>> workingOriginal = new List<KeyValuePair<int,T>>();
    List<T> workingDesired = desired.ToList();
    List<string> operations = new List<string>(); //using Queue<> is ok too

    // load workingOriginal
    foreach(T element in original)
        workingOriginal.Add(new KeyValuePair<int, T>(workingDesired.IndexOf(element), element));

    //1. Remove all elements from the original that are not in the desired list; 
    //   add each remove operation to the list of operations.
    var tempWorking = new List<KeyValuePair<int,T>>(workingOriginal);
    foreach (var element in tempWorking)
    {
        if (!workingDesired.Contains(element.Value))
        {
            workingOriginal.Remove(element);
            operations.Add("remove(" + element.Value.ToString() + ")");
        }
    }

    //2. Add any elements to working that are missing;
    //   add each add operation to the list of operations.
    tempWorking = new List<KeyValuePair<int,T>>(workingOriginal);
    foreach(T element in workingDesired)
    {
        if(!workingOriginal.Exists(x=>x.Value.Equals(element)))
        {
            workingOriginal.Add(new KeyValuePair<int, T>(workingDesired.IndexOf(element), element));
            operations.Add("add("+element+")");
        }
    }

    //3. Assign to each element of the original list a "order number" 
    //   which is the position of its analog in the desired list.
    
    // note: already done above. would have done it here, but
    //       KeyValuePair.Key is read-only.

    //4. Find the first element (0 at original[1]) and the 
    //   last element in order from there (1 at original[2]).
    int indexOfFirstElement = workingOriginal.FindIndex(x => x.Key == 0);
    int indexOfLastElement = indexOfFirstElement;

    // move to index of last in-order element
    for (int i = indexOfLastElement + 1;
         i < workingOriginal.Count &&
         workingOriginal[i - 1].Key + 1 == workingOriginal[i].Key;
         i++, indexOfLastElement++) ;
    
    //5. Remove all elements at positions outside of this range and put them in some
    //   other temporary list; add each remove operation to the list of operations.
    List<KeyValuePair<int, T>> temporary = new List<KeyValuePair<int, T>>();
    var inOrderElements = workingOriginal.GetRange(
                            indexOfFirstElement, 
                            indexOfLastElement - indexOfFirstElement + 1);
    var outOfOrderElements = new List<KeyValuePair<int, T>>(
                                workingOriginal.Except(inOrderElements));

    foreach (var element in outOfOrderElements)
    {
        workingOriginal.Remove(element);
        temporary.Add(element);
        operations.Add("remove(" + element.Value.ToString() + ")");
    }

    //6. Sort the temporary list based on the "order number".
    temporary.Sort((x, y) => { return x.Key.CompareTo(y.Key); });

    //7. Add the elements in order from the temporary list; 
    //   add each add operation to the list of operations.
    foreach (var element in temporary)
    {
        workingOriginal.Add(element);
        operations.Add("add(" + element.Value.ToString() + ")");
    }

    //8. Verify that this newly transformed list matches the desired list.
    var newlyTransformed = workingOriginal.ConvertAll<T>(x => { return x.Value; });
    if (!newlyTransformed.SequenceEqual(desired))
    {
        // this should never happen
        throw new StackOverflowException("FAILED");
    }

    //9. Return the list of operations.
    return operations;
}

Answer 3

头脑风暴：

• 任意排序可以被认为是一种给定适当比较函数的排序。
• 笛卡尔树有一个有趣的属性，它模拟了列表的原始顺序（通过就地遍历）和列表的排序顺序（作为堆）。

也许您可以使用笛卡尔树来确定操作顺序，如下所示（经过编辑以修复在完成以下示例时发现的错误）：

• 调用原始列表 L。
• 从 L 构造笛卡尔树 T。这需要 O(n) 时间。
• 构造一个空优先级队列 Q。
• 分配节点 N = T 的根（这是列表中尚未处理的最小项目）。
• 重复以下步骤，直到 Q 为空且 N 为 null。
  • 从 L 中删除 N 的所有左子项并将它们放在 Q 上。项目 N 现在位于 L 上。
  • 指定 N = N 的右子节点。
  • 如果 N < Q的头：从L中删除N并将其放在Q上。
  • 当 Q 的 head <= N 或 N==null 时：弹出 Q 并将结果压入 L。

让我们尝试一个例子：

I '将使用维基百科页面中的笛卡尔树中的示例：

开始时：

• L = 9,3,7,1,8,12,10,20,15,18,5
• Q = 空
• N = 1

首先循环：

• 将 N 的左子节点移至 Q：
  • L = 1,8,12,10,20,15,5
  • Q = 3,7,9
• 将 N 重新分配给右子节点：N = 5
• 将 N 移至 Q
  • L = 1,8,12,10,20,15
  • Q = 3,5,7,9
• 将 <= N 的项从 Q 推到 L 上：
  • L = 1,8,12,10,20,15,3,5
  • Q = 7,9

第二个循环：

• 将 N 的左子节点移至 Q：
  • L = 1,3,5
  • Q = 7,8,9,10,12,15,20
• 将 N 重新分配给右子节点： N = null
• 将剩余项目从 Q 推送到 L：
  • L = 1,3,5,7,8,9,10,12,15,20

完成。