在给定条件下合并列表中的项

Question

假设我有['A B', 'B C', 'X Y', 'C D', 'Y Z', 'D E', 'C G']

如果列表中每个元素的第二个单词与列表中任何其他元素的第一个单词相同，则应将它们合并为一个项。顺序也很重要。

['A B C D E G', 'X Y Z']应为最终产物。

字母不会形成一个循环，即['A B', 'B C', 'C A']是不可能的。

至于为什么最后加入G，假设我们在'A B C'，我们看到'C D'。在后面的列表中我们有'C G'。我们加上'C D'，因为它先出现，所以我们有'A B C D'，然后如果有'D E'，我们将其合并到'A B C D E'。现在，在"链"的末端，我们添加'C G'，所以我们有'A B C D E G'。如果有'B H'，既然B在前面，那么它应该是'A B C D E H G'。

由于顺序问题，由于B没有连接到c,['A B', 'C A']仍然是['A B', 'C A']。

另一个例子是:

如果我们有['A B', 'A C']，那么在第一步我们只有A B，然后我们看到A C，我们把它合并到A B，我们有A B C。

我尝试了很多东西，比如把每个元素分解成两个列表，然后索引和删除等。它太复杂了，我觉得应该有一个更直观的方法在Python中解决这个问题。唉，我似乎想不明白。

Answer 1

解决这个问题的一个简单算法似乎是:

• 将results初始化为空列表
对输入列表中的每个对重复
• :
  • 对results中的每个子列表R重复:
    • 如果R包含对的第一项，将第二项附加到R并继续下一项
  • 如果子列表R不包含对的第一项，则将对作为新子列表追加到results

Python中的实现很简单，应该是不言自明的:

def merge_pairs(pairs):
results = []
for pair in pairs:
first, second = pair.split()
for result in results:
if first in result:
result.append(second)
break
else:
results.append([first, second])
return [' '.join(result) for result in results]

唯一额外的步骤是由.split()和' '.join()在空格分隔的字母和字母列表之间进行转换。

注意for语句的else子句，它只在没有遇到break时执行。

一些例子:

>>> merge_pairs(['A B', 'B C', 'X Y', 'C D', 'Y Z', 'D E', 'C G'])
['A B C D E G', 'X Y Z']
>>> merge_pairs(['A B', 'A C'])
['A B C']
>>> merge_pairs(['B C', 'A B'])
['B C', 'A B']

Answer 2

有点乱，但这是可行的。

=("AB"、"公元前"、"XY"、"CD","YZ"、"德"、"CG")

used_item = []
result = []
for f, fword in enumerate(a):
for s, sword in enumerate(a):
if f == s:
continue
if fword[1] == sword[0]:
if f in used_item or s in used_item:
idx = [i for i, w in enumerate(result) if fword[1] in w][0]
result = [r + sword[1] if i == idx else r for i, r in enumerate(result) ]  
used_item.append(f)
used_item.append(s)


else:
result.append(fword+sword[1])
used_item.append(f)
used_item.append(s)

print(result)

输出为['ABCDGE'， 'XYZ']如有必要，您可以对'ABCDGE'进行排序。

Answer 3

我很欣赏以上所有的答案，并想尝试使用图论的问题。

这个问题是一个经典的连接组件的例子，其中我们可以为每个节点分配一个unique identifier(节点是列表中的不同字符= a, B, C， ....)相应的Z)。

同时，由于我们需要保持顺序，DFS是继续的正确选择。

Algorithm:
1. Treat the characters A, B, C, .... Z as different 26 nodes.
2. Perform DFS on each node.
2.1 If the node has not been assigned an unique identifier:
2.1.1. Assign a new unique identifier to the node.
2.1.2. dfs(node)

2.2 Else:
no nothing

函数dfs()将根据unique identifier对节点进行分组。执行DFS时，子节点得到与相同的unique identifier作为父元素

看一下下面的实现:

class Graph:

def __init__(self, n):
self.number_of_nodes = n
self.visited = []
self.adjacency_list = []
self.identifier = [-1] * self.number_of_nodes
self.merged_list = []

def add_edge(self, edge_start, edge_end):
if(self.encode(edge_end) not in self.adjacency_list[self.encode(edge_start)]):
self.adjacency_list[self.encode(edge_start)] = self.adjacency_list[self.encode(edge_start)] + [self.encode(edge_end)]

def initialize_graph(self):
self.visited = [False] * self.number_of_nodes
for i in range(0, self.number_of_nodes):
self.adjacency_list = self.adjacency_list + [[]]
def get_adjacency_list(self):
return self.adjacency_list
def encode(self, node):
return ord(node) - 65

def decode(self, node):
return chr(node + 65)

def dfs(self, start_index):

if(self.visited[self.encode(start_index)] == True):
return

self.visited[self.encode(start_index)] = True

for node in self.adjacency_list[self.encode(start_index)]:

if(self.identifier[node] == -1):
self.identifier[node] = self.identifier[self.encode(start_index)]

if(self.visited[node] == False):
self.merged_list[self.identifier[node]] = self.merged_list[self.identifier[node]] + self.decode(node)

self.dfs(self.decode(node))                
graph = Graph(26)
graph.initialize_graph()
input_list = ['A B', 'B C', 'X Y', 'C D', 'Y Z', 'D E', 'C G']
for inputs in input_list:
edge = inputs.split()
edge_start = edge[0]
edge_end = edge[1]
graph.add_edge(edge_start, edge_end)

unique_identifier = 0
for inputs in input_list:
edge = inputs.split()
edge_start = edge[0]

if(graph.identifier[graph.encode(edge_start)] == -1):
graph.identifier[graph.encode(edge_start)] = unique_identifier
graph.merged_list = graph.merged_list + [edge_start]
unique_identifier = unique_identifier + 1
graph.dfs(edge_start)
print(graph.merged_list)

输出:

['ABCDEG', 'XYZ']