Python实现列表含公共元素项的排序与分组方法问询

To solve this problem, we can model the connections between elements as directed chains, where each element's tuple (a, b) links to the element whose tuple starts with b. Here's a straightforward, efficient implementation:

Approach #

1. Create a lookup map: Build a dictionary that maps the first value of each tuple to the full element. This lets us quickly find the next element in the chain using the current element's second tuple value.
2. Find starting points: Identify elements with no incoming links—these are elements where their tuple's first value doesn't appear as the second value in any other element.
3. Traverse each chain: For each unvisited starting point, follow the chain of elements until there are no more links, collecting elements into a group. Mark elements as visited to avoid reprocessing.

Code Implementation #

ev = (('A',(1,2)), ('M',(0,40)),('S',(17,32)),('Z',(2,7)),('K',(7,12)),('U',(40,18)),('R',(32,5)),('V',(28,47)),('X',(5,28)))

# Build a map from tuple's first value to the corresponding element
forward_map = {a: (letter, (a, b)) for letter, (a, b) in ev}

# Collect all second values from tuples to identify start points
all_b_values = {b for _, (_, b) in ev}

visited = set()
result = []

# Iterate through elements to build groups
for elem in ev:
    _, (a, _) = elem
    if elem not in visited and a not in all_b_values:
        group = []
        current = elem
        while current is not None:
            group.append(current)
            visited.add(current)
            # Get the next element using the current tuple's second value
            next_a = current[1][1]
            current = forward_map.get(next_a)
        result.append(tuple(group))

grp = tuple(result)
print(grp)

Efficiency #

This solution runs in O(n) time complexity, where n is the number of elements. Every element is processed exactly once during map creation, start point detection, and chain traversal. Space complexity is also O(n) to store the lookup map, visited set, and result groups.

Edge Cases #

• Isolated elements: Any element that doesn't link to or from another will form its own group.
• Cycles: This code assumes no cyclic links (e.g., an element that points back to a previous element in the same chain). If cycles are possible, add checks to track elements in the current group and break loops when a cycle is detected.

内容的提问来源于stack exchange，提问作者maxime neko