C#: Приоритизация/реорганизация строкового массива

Я работаю над проблемой, где я должен предоставить список строк, и мне нужно организовать их таким образом, чтобы возвращал список строк в правильном порядке. Получаемый массив строк содержит шаги и необходимый шаг для выполнения задачи.C#: Приоритизация/реорганизация строкового массива

Пример входные данные массив:

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

Массив организован таким образом, что первая строка является основным шагом и предварительно REQ требуется после того, как толстая кишка. Если на шаге нет предварительного запроса, он будет пустым. С массивом выше ожидаемого результата будет: Шаг A, Шаг D, Шаг B, Шаг F, Шаг C, Шаг E

Я пытаюсь придумать, как наилучшим образом подойти к этой и какой структуре данных (s) для использования. Моя первая мысль заключалась в том, чтобы пропустить через массив и получить Шаги без предварительного добавления их в список. Затем мне нужно было бы снова ввести входной массив.

источник

2016-06-26 btjordan23

Как можно выполнить шаг D перед шагом B? – Kld

@ Kld - Я считаю, что OP ищет [Топологический вид] (https://www.bing.com/search?q=c%23+topological+sort). –

@AlexeiLevenkov Приносим извинения за возобновление вопроса, пока намерение было просто проголосовать за повторное открытие. Я согласен, что ОП просит какой-то топологический сорт, но не может понять, как он примет ответы. Из желаемых результатов кажется, что достаточно простого поиска и испускания его в первом порядке хлеба. Но, пожалуйста, закройте его, если вы считаете, что он должен быть закрыт. И снова приношу свои извинения. –

Глядя на ожидаемый выход, проблема может быть эффективно решена путем создания дерева зависимостей с помощью ToLookup, где ключ является предварительно шагом и элементы являются почтовые шаги, а просто выбрасывают его в 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; 
}

источник

2016-06-28 08:14:48

Это дает мне отличное направление для этого. Большое спасибо @Ivan – btjordan23

Рассматривая это с наивным подходом, я бы сказал, что сначала перечислите шаги без требований, а затем перечислите все шаги, для которых требуются уже предпринятые шаги, и повторите.

Любые оставшиеся шаги выполняются в кругах или требуют шага, который не существует.

источник

2016-06-26 17:56:31

C#: Приоритизация/реорганизация строкового массива

ответ

Смежные вопросы