如何按元素首次出现顺序排序列表并聚合相同元素？

Got it, let's break down how to solve this problem. The goal is to write a function that groups identical elements together, keeping the groups in the order each unique element first appeared in the input. If all elements are unique, we just return the original list as-is.

First, let's confirm the expected behavior with the given assertions:

assert list(appearance_sort([3, 5, 4, 3, 6, 4])) == [3, 3, 5, 4, 4, 6]
assert list(appearance_sort(['apple', 'apple', 'banana', 'grape', 'banana'])) == ['apple', 'apple', 'banana', 'banana', 'grape']
assert list(appearance_sort([13, 28, 69, 72])) == [13, 28, 69, 72]
assert list(appearance_sort([])) == []
assert list(appearance_sort([1])) == [1]

Approach #

The core idea is to track two key pieces of information as we iterate through the input:

• First occurrence order: A list that records the sequence each unique element first shows up (this determines the order of our groups).
• Element frequency: A dictionary that counts how many times each element appears (this tells us how many times to repeat each element in its group).

Once we have these, we can build the final result by expanding each element in the first-occurrence order according to its frequency.

Solution Code #

Here's a straightforward implementation that works for any iterable, no external dependencies needed:

def appearance_sort(iterable):
    # Track the order each unique element first appears
    first_occurrence = []
    # Count how many times each element appears
    frequency = {}
    
    for elem in iterable:
        # Add to first_occurrence only if we haven't seen this element before
        if elem not in first_occurrence:
            first_occurrence.append(elem)
        # Update the frequency count
        frequency[elem] = frequency.get(elem, 0) + 1
    
    # Build the result by repeating each element according to its frequency
    result = []
    for elem in first_occurrence:
        result.extend([elem] * frequency[elem])
    
    return result

If you prefer a memory-efficient generator-based approach (great for large datasets), you can modify it to yield elements instead:

def appearance_sort(iterable):
    first_occurrence = []
    frequency = {}
    
    for elem in iterable:
        if elem not in first_occurrence:
            first_occurrence.append(elem)
        frequency[elem] = frequency.get(elem, 0) + 1
    
    for elem in first_occurrence:
        yield from [elem] * frequency[elem]

How It Works #

Let's walk through the first example to see the process:

1. Input: [3, 5, 4, 3, 6, 4]
2. first_occurrence becomes [3, 5, 4, 6] (we add each element only the first time we encounter it)
3. frequency becomes {3:2, 5:1, 4:2, 6:1}
4. We build the result by expanding each element in first_occurrence:
   • 3 repeated 2 times → [3,3]
   • 5 repeated 1 time → [5]
   • 4 repeated 2 times → [4,4]
   • 6 repeated 1 time → [6]
5. Combining these gives [3,3,5,4,4,6], which matches the assertion.

This approach naturally handles all edge cases (empty input, single-element input, all unique elements) and strictly maintains the required group order based on first occurrence.

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