阵列组映射

Question

现在他们的分组应如下：

[Q,W,E,R] - Group 1
[A,S,D,F] - Group 2
[Z,X,C,V] - Group 2 (Because of connecting array element in row 5)
[P,O,I,R] - Group 1
[L,J,A,Z] - Group 2 (Connecting element in row 2)

最终输出：

Q, Group 1
W, Group 1
E, Group 1
R, Group 1
A, Group 2
S, Group 2
D, Group 2
F, Group 2
Z, Group 2
X, Group 2
C, Group 2
V, Group 2
P, Group 1
O, Group 1
I, Group 1
L, Group 2
J, Group 2

我很困惑用于解决此问题的图形结构。

HERHE是Python中可能的解决方案：

def group_ids(arrays):
    """
    Groups IDs from a list of arrays based on shared elements.

    Args:
        arrays: A list of arrays (lists).

    Returns:
        A dictionary mapping each ID to its group name.
    """

    # Create a graph representation using an adjacency list.
    graph = {}
    for array in arrays:
        for item in array:
            if item not in graph:
                graph[item] = set()
            for other_item in array:
                if item != other_item:
                    graph[item].add(other_item)

    # Perform Depth-First Search (DFS) to find connected components.
    visited = set()
    groups = {}
    group_count = 1

    def dfs(node, group_name):
        visited.add(node)
        groups[node] = group_name
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, group_name)

    # Iterate through all unique IDs and assign them to groups.
    all_ids = set()
    for array in arrays:
      for item in array:
        all_ids.add(item)

    for item in all_ids:
      if item not in visited:
          dfs(item, f"Group {group_count}")
          group_count += 1

    return groups

# Example usage:
arrays = [
    ['Q', 'W', 'E', 'R'],
    ['A', 'S', 'D', 'F'],
    ['Z', 'X', 'C', 'V'],
    ['P', 'O', 'I', 'R'],
    ['L', 'J', 'A', 'Z']
]

result = group_ids(arrays)

# Print the results:
for item, group in result.items():
    print(f"{item}, {group}")

解释：

Answer 1

图表（邻接列表）：

我们使用词典
1. graph

   表示ID之间的关系。

   EACHID是字典中的键，其值是其“邻居”的集合（其他出现在同一数组中的ID）。
   this这有效地创建了一个无向图，其中ID是节点，并且边缘连接在同一数组中的ID。
   深入搜索（DFS）：

   • dfs

     函数探索图形以查找连接的组件。
它采用
2. node

   （id）和agroup_name作为输入。

   • 将节点标记为

     visited

     ，将其分配给给定的组，并递归地为所有未访问的邻居呼唤。
     

   通过使用访问的套件，我们避免了无限的循环，我们保证每个节点只访问一次。

   • 组：

   • 我们遍历所有独特的IDS。
     

   对于每个未访问的ID，我们启动了一个新的DFS Traversal，将所有连接的ID分配给同一组。

   • 我们为每个新组增量。

3. 输出：

   • 字典将ID的最终映射存储给其组名称。

   • 我们通过字典迭代并打印结果。

   • 为什么图形结构？

问题自然会适合图表表示，因为我们正在处理元素之间的关系（共享数组成员）。

4. DFS是用于在图中查找连接组件的标准算法，这正是我们对ID分组所需的内容。

   图表的邻接列表表示对此任务有效，尤其是在处理潜在的大量ID和数组时。