如何实现DataFrame列无相邻重复元素排序？求该排序方法学名

一、正式技术名称 #

这种将序列重排为无相同元素相邻的问题，属于序列重排类问题，常用的贪心解法对应的场景可称为**“最大频次优先的无相邻重复重排”，也可归类到“重构字符串/序列”**问题范畴（类似经典算法题“重构字符串”的题型）。核心思路是通过贪心策略，优先放置出现次数最多的元素，再用其余元素穿插填充，避免相邻重复。

二、Pandas DataFrame的实现方案 #

针对你的DataFrame，可通过以下步骤实现需求：

1. 统计每个item的出现频次，同时保留原数据的行关联信息；
2. 利用最大堆（优先队列）按频次从高到低取元素，构建无相邻重复的序列；
3. 将构建好的序列映射回原DataFrame，保留person列的对应关系。

具体代码 #

import pandas as pd
import heapq

df = pd.DataFrame({
    'item':['A', 'A', 'A', 'B', 'B', 'C', 'E'],
    'person':[1, 1, 2, 2, 2, 2, 1]
})

# 1. 统计每个item的频次，同时为每个item创建原行的迭代器
item_counts = df['item'].value_counts().to_dict()
item_iterators = {
    item: iter(df[df['item'] == item].itertuples(index=False)) 
    for item in item_counts
}

# 提前判断是否能实现无相邻重复排序
max_count = max(item_counts.values())
if max_count > (len(df) + 1) // 2:
    raise ValueError("无法实现无相邻重复的排序：某元素频次超过总长度的一半")

# 2. 构建最大堆（Python堆默认是最小堆，存储负频次实现最大堆逻辑）
heap = [(-count, item) for item, count in item_counts.items()]
heapq.heapify(heap)

result = []
prev_item = None

while heap:
    neg_count, current_item = heapq.heappop(heap)
    # 若当前元素和上一个相同，先取堆中下一元素暂存当前
    if current_item == prev_item and heap:
        temp_neg, temp_item = neg_count, current_item
        neg_count, current_item = heapq.heappop(heap)
        heapq.heappush(heap, (temp_neg, temp_item))
    
    # 从迭代器中取出对应行加入结果
    row = next(item_iterators[current_item])
    result.append({'item': row.item, 'person': row.person})
    prev_item = current_item
    
    # 若当前元素还有剩余，放回堆中
    if neg_count + 1 < 0:
        heapq.heappush(heap, (neg_count + 1, current_item))

# 3. 生成最终排序后的DataFrame
sorted_df = pd.DataFrame(result)
print(sorted_df)

代码说明 #

• 最大堆确保每次优先处理出现次数最多的元素，从根源降低相邻重复的概率；
• 通过临时缓存相同元素的逻辑，直接避免连续放置同一元素；
• 用迭代器关联原数据行，确保person列与item的对应关系不丢失；
• 提前判断频次阈值，避免出现无法完成重排的死循环。

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