быстрый алгоритм для «кругового связанного списка строитель»

Question

У меня есть два вопроса:

1) Какой самый быстрый алгоритм, чтобы положить этот список в разделе «Подключение» порядка?
2) Является ли это существующей проблемой/алгоритмом, и какое имя оно имеет?

Узлы всегда соединены круговым способом, поэтому мой начальный идентификатор не имеет значения.

Учитывая этот список:

id node1 node2 
A 4  9 
B 6  1 
C 1  3 
D 3 10 
E 7  2 
F 4  2 
G 9  8 
H 10  5 
I 7  5 
J 6  8 

node1 & node2 не в определенном порядке, идентификатор А может быть 4 - 9, а также 9 - 4.

Вывод должен быть таким (это не имеет значения, начинается ли оно с A, пока выход представляет собой цепочку).

node ids: 4 - 9 - 8 - 6 - 1 - 3 - 10 - 5 - 7 - 2 - 4 
ids:  A G J B C D H I E F 

(я пишу свой код в C#. Но псевдо-код на любом языке будет делать)

Answer 1

Вы можете сделать это следующим образом:

static IEnumerable<Edge<T>> OrderEdges<T>(this IEnumerable<Edge<T>> edges) 
    where T : IEquatable<T> 
{ 
    Debug.Assert(edges.Any()); 
    var map = new Dictionary<T, Edge<T>>(); 

    foreach (var e in edges) 
    { 
     if (map.ContainsKey(e.Node1)) 
     { 
      Debug.Assert(!map.ContainsKey(e.Node2)); 
      map.Add(e.Node2, e); 
     } 
     else 
     { 
      map.Add(e.Node1, e); 
     } 
    } 

    var current = edges.First(); 
    var orderedEdges = new HashSet<Edge<T>>(); 

    while (true) 
    { 
     orderedEdges.Add(current); 
     yield return current; 

     if (orderedEdges.Count == map.Count) 
      break; 

     var next = map[current.Node2]; 
     current = orderedEdges.Contains(next) ? map[current.Node1] : next; 
    } 
} 

Где Edge<T> класс просто:

class Edge<T> where T: IEquatable<T> 
{ 
    public T Node1 { get; } 
    public T Node2 { get; } 
    public string Name { get; } 
    public Edge(string name, T node1, T node2) 
    { 
     Name = name; 
     Node1 = node1; 
     Node2 = node2; 
    } 

    public override string ToString() => Name; 
} 

Если мы запустим этот маленький парень:

var edges = new List<Edge<int>>() { 
    new Edge<int>("A", 4, 9), new Edge<int>("B", 6, 1), 
    new Edge<int>("C", 1, 3), new Edge<int>("D", 3, 10), 
    new Edge<int>("E", 7, 2), new Edge<int>("F", 4, 2), 
    new Edge<int>("G", 9, 8), new Edge<int>("H", 10, 5), 
    new Edge<int>("I", 7, 5), new Edge<int>("J", 6, 8) }; 

Console.WriteLine(string.Join(" -> ", edges.OrderEdges())); 

Мы получаем ожидаемый результат:

A -> G -> J -> B -> C -> D -> H -> I -> E -> F 

Обратите внимание, что это решение предполагает, что входные данные хорошо сформированы.

Answer 2

Я считаю, что вы ищете Eulerian path

Answer 3

Я не знаю, является ли это некоторые математические проблемы. Вот псевдокод, который позволяет решить проблему в O (N) манере (сложность и использование памяти).

1) Создать массив (мы предполагаем, что узлы имеют уникальные идентификаторы из диапазона [0..N-1]. И заполнить его с узлами (узел с идентификатором должен быть помещен в позицию ид)

2) выбрать любой узел и нажмите его в отдельный список (он будет содержать Node в «круговом» порядке). Последний узел в этом списке будет называться как обработанный узел.

3) итерация от 1 до N -1 на каждом шаге выбирает не пройденный сосед обработанного узла. Нажимайте такой непересекающийся узел в круглый список. Продолжить процесс

Примечание: проверка свойства «не пройдена» может выполняться способом O (1). Просто посмотрите, где он уже присутствует в круговом списке. Он должен быть соседом последнего (обработанного) узла

Главный недостаток - предположение о таком алгоритме - существование единственного пути Эйлера.

Answer 4

Вот предложение, используя словарь (хеш-таблицу) для расчетов.

Я назвал «ячейку» строкой листа, представленной в вопросе (но мы не знаем вашу структуру данных).

Кажется, что O (n) в качестве словарей обеспечивает извлечение O (1).

Все это предполагает, что исходные данные соответствуют задаче (как я понял, по крайней мере).

Код находится на C# и прокомментирован. Скажите, если комментариев недостаточно для объяснений.

class Program 
{ 
    class Cell 
    { 
     public string Id { get; set; } 
     public int Node1 { get; set; } 
     public int Node2 { get; set; } 

     public int Min { get { return Math.Min(Node1, Node2); } } 

     public Cell(string name, int node1, int node2) 
     { 
      Id = name; 
      Node1 = node1; 
      Node2 = node2; 
     } 

     public override string ToString() 
     { 
      return Id + "(" + Node1.ToString() + "," + Node2.ToString() + ")"; 
     } 
    } 

    static void Main(string[] args) 
    { 
     var A = new Cell("A", 4, 9); 
     var B = new Cell("B", 6, 1); 
     var C = new Cell("C", 1, 3); 
     var D = new Cell("D", 3, 10); 
     var E = new Cell("E", 7, 2); 
     var F = new Cell("F", 4, 2); 
     var G = new Cell("G", 9, 8); 
     var H = new Cell("H", 10, 5); 
     var I = new Cell("I", 7, 5); 
     var J = new Cell("J", 6, 8); 

     var cells = new List<Cell>() { A, B, C, D, E, F, G, H, I, J }; 

     // A dictionary to store the cells corresponding to each node values 
     Dictionary<int, List<Cell>> dict = new Dictionary<int, List<Cell>>(); 

     // Add all the cells to the dictionary 
     foreach (var cell in cells) 
      AddCell(dict, cell); 

     // Start with arbitrary first cell and remove it from the dictionary 
     var currentCell = GetCell(dict, A.Node1); 
     RemoveCell(dict, currentCell); 

     // The result is a list of cells initialized with the first cell 
     var result = new List<Cell>() { currentCell }; 

     // Calculation loop 
     bool doContinue = true; 
     while (doContinue) 
     { 
      // Tries to get a next cell from the node1 of current cell... 
      var nextCell = GetCell(dict, currentCell.Node1); 

      // ... or if not found, tries to get it from node2 
      if (nextCell == null) 
       nextCell = GetCell(dict, currentCell.Node2); 

      if (nextCell == null) 
      // If not found, we stop 
      { 
       doContinue = false; 
      } 
      else 
      // If found 
      { 
       // Add the next cell to the result 
       result.Add(nextCell); 
       // Remove the cell 
       RemoveCell(dict, nextCell); 
      } 

      // The next cell becomes the current cell 
      currentCell = nextCell; 
     } 

    } 

    // Adding a cell puts the cell against its two nodes values 
    static void AddCell(Dictionary<int, List<Cell>> dict, Cell cell) 
    { 
     List<Cell> cells = null; 
     if (dict.TryGetValue(cell.Node1, out cells) == false) 
     { 
      cells = new List<Cell>(); 
      dict[cell.Node1] = cells; 
     } 
     cells.Add(cell); 
     if (dict.TryGetValue(cell.Node2, out cells) == false) 
     { 
      cells = new List<Cell>(); 
      dict[cell.Node2] = cells; 
     } 
     cells.Add(cell); 
    } 

    // Gets a cell from a node value 
    static Cell GetCell(Dictionary<int, List<Cell>> dict, int node) 
    { 
     var cell = null as Cell; 
     var cells = dict[node]; 

     if (cells.Count > 0) 
      cell = cells.First(); 

     return cell; 
    } 

    // Removes a cell from the dictionary for both node1 and node2 entries. 
    static void RemoveCell(Dictionary<int, List<Cell>> dict, Cell cell) 
    { 
     dict[cell.Node1].Remove(cell); 
     dict[cell.Node2].Remove(cell); 
    } 
} 

Answer 5

Отправной точкой является список или массив, как:

1 {A, 4, 9} 
2 {B, 6, 1} 
3 {C, 1, 3} 
4 {D, 3,10} 
5 {E, 7, 2} 
6 {F, 4, 2} 
7 {G, 9, 8} 
8 {H,10, 5} 
9 {I, 7, 5} 
10 {J, 6, 8} 

Если мы можем изменить это в виде списка или массива, как это:

1 {C, 1, 3} 
2 {F, 2, 4} (nodes swapped) 
3 {D, 3,10} 
4 {A, 4, 9} 
5 {I, 5, 7} (nodes swapped) 
6 {B, 6, 1} 
7 {E, 7, 2} 
8 {J, 8, 6} (nodes swapped) 
9 {G, 9, 8} 
10 {H,10, 5} 

, который заказывается в соответствии с node1 , то мы можем прочитать этот список или массив как связанный список:

start with item 1: {C, 1, 3} 
read node2: 3 
skip to item 3:  {D, 3,10} 
read node2: 10 
skip to item 10: {H,10, 5} 
... 
skip to item 6:  {B, 6, 1} 
read node2: 1 
end of list 

result: C D H I E F A G J B 

Создание этой второй версии списка можно сделать на месте, путем замены элементов в списке или путем копирования элементов в новый список (если у вас есть пробел).

Единственное, на что нужно обратить внимание, это то, что иногда вам может потребоваться обмен двумя узлами. При повторном упорядоченность в месте, это может пойти как это:

look at item 1:  {A, 4, 9} 
    if item 4 has a node1 different from 4, swap item 1 and 4 
    else, change item 1 to {A, 9, 4} and swap item 1 and 9 
    (-> item 1 and 4 swapped)  

while current item is already in-place, skip to next 
(-> stay at item 1) 

look at new item 1: {D, 3,10} 
    if item 3 has a node1 different from 3, swap item 1 and 3 
    else, change item 1 to {D,10, 3} and swap item 1 and 10 
    (-> item 1 and 3 swapped) 

while current item is already in-place, skip to next 
(-> item 1 is now {C, 1, 3}, so skip to item 2) 

... 

При создании нового списка или массива, то это должно быть еще проще:

look at item 1:  {A, 4, 9} 
    if new list has no item 4, copy item 1 as item 4 to the new list 
    else, change item 1 to {A, 9, 4} and copy as item 9 to the new list 
move to next item 

Как вы можете видеть, нет необходимо многократно перебирать список; каждый элемент заменяется или копируется один раз, а его назначение определяется его узлом1 или узлом2.

---

ОБНОВЛЕНИЕ

Я просто понял, что количество шагов, чтобы заказать товар может быть (много) больше, чем описано выше. Если, например, вы начинаете с перемещения {A, 4,8} до местоположения 4 и {B, 5,9} до местоположения 5, а затем вы сталкиваетесь с {C, 4,5}, вы застреваете. Затем вам придется поменять {C, 4,5} одним из двух других элементов, поменять местами в другом элементе и переместить их на место. Это новое место уже может быть принято и так далее, поэтому не было бы способа узнать, какой из двух вариантов - меньшее зло. В худшем случае количество свопов будет близко к N .

---

ОБНОВЛЕНИЕ 2

Проблема уже упоминалось выше, конечно, можно решить путем сохранения элементов в виде двусвязного списка. Когда вы сталкиваетесь, например, {A, 4,8}, вы храните {A, 8} как элемент 4 и {A, 4} как элемент 8, а затем для {B, 5,9} вы храните {B, 9} элемент 5 и {B , 5} в качестве пункта 9, а затем для {C, 4,5}, вы добавляете к уже сохраненным элементам, так что элемент 4 становится {A, 8, C, 5}, а элемент 5 становится {B, 9, C , 4}. Затем вы можете пересечь двусвязный список в обоих направлениях. Это увеличит работу, которую необходимо выполнить, и используемое пространство, но оно по-прежнему является линейным по количеству элементов в списке.