c#:对字符串数组进行优先级排序/重组

本文关键字：优先级 排序 重组 字符串 数组 | 更新日期: 2023-09-27 17:49:21

我正在解决一个问题，我要提供一个字符串列表，我需要以一种以正确顺序返回字符串列表的方式组织它们。我接收的字符串数组包含步骤和完成任务的先决条件步骤。

输入数组示例:

[
"Step A: ",
"Step B: Step A",
"Step C: Step D",
"Step E: Step C", 
"Step D: ",
"Step F: Step A", 
]

数组的组织方式如下:第一个字符串是主要步骤，所需的前置条件在冒号之后。如果一个步骤没有预先要求，它将为空白。使用上面的数组，预期的输出将是:步骤A，步骤D，步骤B，步骤F，步骤C，步骤E

我正在考虑最好的方法来处理这个问题，以及使用什么数据结构。我的第一个想法是遍历数组并获得步骤，而不需要预先请求将它们添加到列表中。然后我需要再次遍历输入数组

c#:对字符串数组进行优先级排序/重组

看看预期的输出，这个问题可以通过使用ToLookup创建一个依赖树来有效地解决，其中键是pre step，元素是post steps，并简单地以BFS顺序发出:

string[] input =
{
    "Step A: ",
    "Step B: Step A",
    "Step C: Step D",
    "Step E: Step C",
    "Step D: ",
    "Step F: Step A",
};
var output = new string[input.Length];
var separator = new[] { ": " };
var postSteps = input
    .Select(s => s.Split(separator, StringSplitOptions.RemoveEmptyEntries))
    .ToLookup(tokens => tokens.Length > 1 ? tokens[1] : null, tokens => tokens[0]);
var nextSteps = postSteps[null]; // start with root
for (int pos = 0, count = 0; count < output.Length; nextSteps = postSteps[output[pos++]])
{
    foreach (var step in nextSteps)
        output[count++] = step;
}

用一种天真的方法来看待这个问题，我会说，首先列出没有需求的步骤，然后列出需要已经采取的步骤的所有步骤，然后重复。

任何剩余的步骤绕圈运行或需要一个不存在的步骤

相关文章：