c# - 使用命令将一个列表转换为另一个列表

Question

我有两个列表，目的是通过使用一系列删除、移动和附加命令将 list1 转换为 list2。

举个例子；给出以下列表

list1 = ['A','B','C']
list2 = ['B','A','D','C']

要发出的命令是:

commands = [
  'append D', 
  'move D,C', #move D over C
  'move B,A' #move B over A 
]

我已经用 C# 编写了一个程序，以非常命令的方式执行此操作。我对不在 list2 中的每个项目发出删除命令。我为不在 list1 中的每个项目发出追加命令。在计算移动命令时，我按顺序从 list2 中取出项目对，如果顺序与 list1 中的顺序不同，则发出移动命令。

我的问题是我有兴趣用 F# 或类似语言以函数式方式编写另一个解决方案。由于我几乎没有函数式编程的经验，所以我无法全神贯注地思考如何解决这个问题。

您将如何以实用的方式解决这个问题？

编辑:我的解决方案

var oldList = new List<char>() { 'A', 'B', 'C', 'D', 'E' };
var newList = new List<char>() { 'C', 'E', 'B', 'D' };

var deletes = oldList.Except(newList).ToList();
var appends = newList.Except(oldList).ToList();

var commands = new List<string>();
commands.AddRange(deletes.Select(x => String.Format("DELETE {0}", x)));
commands.AddRange(appends.Select(x => String.Format("APPEND {0}", x)));

var tmpList = new List<char>(oldList);
tmpList.RemoveAll(deletes.Contains);
tmpList.AddRange(appends);

bool changed = true;
while (changed)
{
    changed = false;
    for (int i = 0; i < newList.Count-1; i++)
    {
        char current = newList[i];
        char next = newList[i+1];
        int currentIndex = tmpList.IndexOf(current);
        int nextIndex = tmpList.IndexOf(next);

        if (currentIndex <= nextIndex) // same ordering, so continue
            continue;

        commands.Add(String.Format("MOVE {0}, {1}", current, next)); // move current over next
        tmpList.RemoveAt(currentIndex);
        tmpList.Insert(nextIndex, current);
        changed = true;
    }
}

Console.WriteLine(String.Join(", ", oldList.ToArray()));
Console.WriteLine(String.Join(", ", newList.ToArray()));
Console.WriteLine(String.Join(", ", tmpList.ToArray()));
Console.WriteLine(String.Join("\r\n", commands.ToArray()));

Answer 1

首先，为了更好的易用性，您应该使用可区分的联合来表示命令，这样您就可以真正轻松地执行它们。此外，由于 F# 列表是链表，因此使用前置而不是附加会更好地进行实际操作。

type Operation<'a> =
  | Delete of 'a
  | Prepend of 'a
  | Swap of 'a * 'b

我们很快就需要一个函数来获取一个列表中的项目，而不是另一个列表中的项目我们称之为-:

let (-) list1 list2 =
  List.filter
    (fun x -> not (List.exists ((=) x) list2))
    list1

太棒了。这使我们能够编写一个函数，该函数接受两个列表并返回一个删除列表，该列表需要从第一个列表中删除所有额外元素以获取第二个列表，以及一个执行相同操作但用于前置操作的函数。

let deletionOps list1 list2 = (list1 - list2) |> List.map Delete
let prependOps list1 list2 = (list2 - list1) |> List.map Prepend

显而易见的下一步是编写一个函数，为我们提供从一个列表到另一个列表所需的所有交换。首先，我们需要一个可以实际交换列表中项目的函数。一个满足需求的简单的可能如下所示:

module List
  /// Replaces all instances of a with b, and vice versa
  let swap a b l =
    l |> List.map (fun x ->
      if e = a then b
      elif e = b then a
      elif e)

现在是有趣的部分，编写 swapOps 函数，告诉我们从一个列表到另一个列表所需的交换:

let rec swapOps listIn listOut =
  match listIn, listOut with
  | _, [] -> []
  | [], _ -> []
  | a :: listIn, b :: listOut when a = b -> swapOps listIn listOut
  | a :: listIn, b :: listOut -> Swap(a, b) :: swapOps (List.swap a b listIn) listOut

快到了!我们需要函数来实际执行这些操作。这是一种编写它们的方法:

let applyOp list op =
  match op with
  | Delete x -> List.filter ((<>) x) list
  | Prepend x -> x :: list
  | Swap(a, b) -> List.swap a b list

let rec applyOps list ops =
  match ops with
  | [] -> list
  | op :: restOps -> applyOps (applyOp list op) restOps

最后，为了将它们结合在一起，您可以编写一些代码来获取两个列表并返回操作，这些操作在执行时会将一个列表转换为另一个列表(假设没有重复元素)。并不是说我的代码绝对可以改进以减少重复:

let ops listIn listOut =
  let dOps = deleteOps listIn listOut
  let listIn = applyOps listIn dOps
  let pOps = prependOps listIn listOut
  let listIn = applyOps listIn pOps
  let sOps = swapOps listIn listOut
  dOps @ pOps @ sOps

您可以使用之前的 applyOps 函数验证这一点。