'circular linked list builder' 的最快算法
Fastest algorithm for a 'circular linked list builder'
我有两个问题：
1) 将此列表按 "connecting" 顺序排序的最快算法是什么？
2) 这是现有的 problem/algorithm，它的名称是什么？
节点始终以循环方式连接，因此我的起始 ID 无关紧要。
鉴于此列表：
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 没有特定的顺序，所以 id A 可以是 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# 编写代码。但是任何语言的伪代码都可以）
我相信您正在寻找 Eulerian path
我不知道这是否是一些命名的数学问题。这是伪代码，它允许您以 O(N) 方式（复杂性和内存使用）解决问题。
1) 创建数组（我们假设节点在[0..N-1]范围内具有唯一ID。并用节点填充它（具有id的节点应放在id位置）
2) 选择任何节点并将其推送到单独的列表中（它将包含 "circular" 顺序的节点）。该列表中的最后一个节点将被命名为已处理节点。
3) 从1迭代到N -1 每一步选择未遍历的已处理节点的邻居。将未遍历的节点推入循环链表。继续进程
注意：检查 "not traversed" 属性 可以以 O(1) 的方式执行。请看，它已经存在于循环列表中的位置。它应该是最后一个（处理过的）节点的邻居
主要缺点 - 这种算法的假设是存在唯一的欧拉路径。
这里建议使用字典（哈希table）进行计算。
我已将问题中提供的 sheet 的一行命名为 "cell"（但我们不知道您的数据结构）。
似乎是 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 );
}
}
起点是列表或数组，如：
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
可以通过交换列表中的项目或将项目复制到新列表（如果您有 space）来创建列表的第二个版本 in-place。
唯一需要注意的是，有时您可能需要交换两个节点。当 re-ordering in-place 时，这可能是这样的：
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} 与其他两项中的一项交换，交换另一项中的节点，然后将其移动到位。那个新位置本身可能已经被占用，依此类推，因此无法知道这两个选项中哪个是较小的邪恶。在最坏的情况下，交换次数将接近 N2。
更新 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}。然后，您可以双向遍历双向链表。这将增加需要完成的工作和使用的space，但它仍然与列表中的项目数成线性关系。
您可以通过以下方式进行：
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 就是：
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
请注意，此解决方案假定输入数据格式正确。
我有两个问题：
1) 将此列表按 "connecting" 顺序排序的最快算法是什么？
2) 这是现有的 problem/algorithm，它的名称是什么？
节点始终以循环方式连接，因此我的起始 ID 无关紧要。
鉴于此列表：
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 没有特定的顺序，所以 id A 可以是 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# 编写代码。但是任何语言的伪代码都可以）
我相信您正在寻找 Eulerian path
我不知道这是否是一些命名的数学问题。这是伪代码，它允许您以 O(N) 方式（复杂性和内存使用）解决问题。
1) 创建数组（我们假设节点在[0..N-1]范围内具有唯一ID。并用节点填充它（具有id的节点应放在id位置）
2) 选择任何节点并将其推送到单独的列表中（它将包含 "circular" 顺序的节点）。该列表中的最后一个节点将被命名为已处理节点。
3) 从1迭代到N -1 每一步选择未遍历的已处理节点的邻居。将未遍历的节点推入循环链表。继续进程
注意：检查 "not traversed" 属性 可以以 O(1) 的方式执行。请看，它已经存在于循环列表中的位置。它应该是最后一个（处理过的）节点的邻居
主要缺点 - 这种算法的假设是存在唯一的欧拉路径。
这里建议使用字典（哈希table）进行计算。
我已将问题中提供的 sheet 的一行命名为 "cell"（但我们不知道您的数据结构）。
似乎是 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 );
}
}
起点是列表或数组，如：
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
可以通过交换列表中的项目或将项目复制到新列表（如果您有 space）来创建列表的第二个版本 in-place。
唯一需要注意的是，有时您可能需要交换两个节点。当 re-ordering in-place 时，这可能是这样的：
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} 与其他两项中的一项交换，交换另一项中的节点，然后将其移动到位。那个新位置本身可能已经被占用，依此类推，因此无法知道这两个选项中哪个是较小的邪恶。在最坏的情况下，交换次数将接近 N2。
更新 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}。然后，您可以双向遍历双向链表。这将增加需要完成的工作和使用的space，但它仍然与列表中的项目数成线性关系。
您可以通过以下方式进行：
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 就是：
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
请注意，此解决方案假定输入数据格式正确。