如何用Python实现相同元素间最小距离最大化的数组重排？

给定数组示例：

arr = ['A', 'A', 'A', 'B', 'B']

需求是对数组重排，让相同元素之间的最小距离尽可能大，最优结果示例为：

arr1 = ['A', 'B', 'A', 'B', 'A']

问题分析与解决方案 #

你尝试的遗传算法容易陷入局部最优，本质是这种编码方式的搜索空间过大，且交叉变异难以精准导向全局最优。更高效可靠的方法是贪心策略：优先放置频率最高的元素，保证其间隔最大化，再用其他元素填充剩余位置。

代码实现 #

from collections import Counter

def rearrange_max_min_distance(arr):
    # 统计各元素出现频率，按频率降序排序
    elem_counts = Counter(arr)
    sorted_elements = sorted(elem_counts.items(), key=lambda x: -x[1])
    
    total_length = len(arr)
    result = [None] * total_length
    current_idx = 0
    
    # 先间隔放置高频元素
    for elem, count in sorted_elements:
        for _ in range(count):
            result[current_idx] = elem
            current_idx += 2
            # 若索引超出数组长度，切换到从奇数位开始填充
            if current_idx >= total_length:
                current_idx = 1
    
    return result

# 测试示例
test_arr = ['A', 'A', 'A', 'B', 'B']
print(rearrange_max_min_distance(test_arr))  # 输出: ['A', 'B', 'A', 'B', 'A']

原理说明 #

1. 频率排序：先统计每个元素的出现次数，把元素按频率从高到低排序，确保高频元素优先得到最大间隔的放置位置。
2. 间隔填充：从索引0开始，每隔一个位置放置一个高频元素，当索引超出数组长度时，切换到从索引1开始继续填充，保证高频元素的间隔尽可能均匀。
3. 填充剩余元素：后续低频元素填充剩下的空位，自然会被高频元素隔开，最终整体的相同元素最小距离达到最大。

这种方法的时间复杂度为O(n log n)（主要来自排序），远优于遗传算法的随机搜索，且能直接构造出最优解，不会陷入局部最优。

内容的提问来源于stack exchange，提问作者João Pedro