连接成对的数字

Question

给定一个成对数字[(13, 4), (8, 12), (8, 4), (13, 2)]的列表，其中每个数字恰好出现一到两次，创建一个"；"链表"；，如果元组共享一个数字，它们在哪里连接？

链接以上元组将返回(2, 13)-(13, 4)-(4, 8)-(8, 12)或仅返回(2-13-4-8-12)(或相反的顺序，一对中的顺序无关紧要(。

(作为第二个问题：这类问题有名字吗？(

Answer 1

如果输入定义了一个单一路径的图，则可以使用此算法。我使用了Python:

from collections import defaultdict
# The function that takes a list of pairs as input and returns the path/chain
def chain(pairs):
# create graph
edges = defaultdict(set)  # each node will be associated with a set of neighbors
for a, b in pairs:
edges[a].add(b)
edges[b].add(a)  # define both the forward as backward edge
# find a node with just one edge
start = pairs[0][0]  # default node
for node, second in edges.items():
if len(second) == 1:
start = node
break
# start at that node and follow the edges
result = [start]
prev = None
while len(result) <= len(pairs):
neighbors = edges[start]
neighbors.discard(prev)  # discard the back referencing edge
prev = start
start = next(iter(neighbors))  # get the only other neighbor
result.append(start)
return result
pairs = [(13, 4), (8, 12), (8, 4), (13, 2)]
print(chain(pairs))

Answer 2

这里有另一种可能的实现，它避免使用图，而是将边连接到子链，直到它们形成单个长链：

def chain(edges):
from collections import deque
link = lambda c, e: (c.appendleft if c[0] == a else c.append)
chains = {}
for a, b in edges:
if a in chains and b in chains:
c1 = chains.pop(a)
c2 = chains.pop(b)
if c1[0] == a: c1.reverse()
if c2[0] != b: c2.reverse()
c1.extend(c2)
chains[c1[-1]] = c1
elif a in chains:
chain = chains.pop(a)
link(chain, a)(b)
elif b in chains:
chain = chains.pop(b)
link(chain, b)(a)
else:
chains[a] = chains[b] = deque([a, b])
return set(map(tuple, chains.values())).pop()
edges = [(13, 4), (8, 12), (8, 4), (13, 2)]
path = chain(edges)

Answer 3

这是基于trincot的答案，避免了图形的突变：

def make_graph(edges):
graph = defaultdict(set)
for a, b in pairs:
edges[a].add(b)
edges[b].add(a
return graph
def find_endpoints(edges):
from collections import Counter
from itertools import chain
return [v for v, count in Counter(chain(*edges)).items() if count == 1]
def find_path(graph, start, end):
chain = [start, next(iter(graph[start]))]
while chain[-1] != end:
for neighbour in graph[chain[-1]]:
if neighbour != chain[-2]:
chain.append(neighbour)
break
return chain
edges = [(13, 4), (8, 12), (8, 4), (13, 2)]
graph = make_graph(edges)
endpoints = find_endpoints(edges)
path = find_path(graph, *endpoints)

Answer 4

如果这对JVM世界的任何人都有帮助，我已经设法将此算法复制为Kotlin函数。

fun chain(pairs: List<Pair<Int, Int>>): MutableList<Int> {
val edges = mutableMapOf<Int, MutableSet<Int>>()
pairs.forEach { (a, b) ->
edges[a] = mutableSetOf()
edges[b] = mutableSetOf()
}
pairs.forEach { (a, b) ->
edges[a]!!.add(b)
edges[b]!!.add(a)
}
if (pairs.isNotEmpty()) {
var start = pairs[0].first
var prev: Int? = null
for ((node, value) in edges.entries) {
if (value.size == 1) {
start = node
break
}
}
val result = mutableListOf(start)
while (result.size <= pairs.size) {
val neighbors = edges[start]
neighbors?.remove(prev)
prev = start
neighbors?.forEach { start = it }
result.add(start)
}
return result
}
return mutableListOf()
}