如何重排列表以最大化重复元素间的最小距离？

问题描述 #

给定列表，例如：[1,1,2,2,3,5]，希望将其重排为：[1,2,3,5,1,2]。

核心目标：最大化任意相同元素两次出现间的最小距离，尽可能分散重复元素，减少其紧密性。

现有思路与实现 #

思路步骤 #

1. 统计所有元素的出现次数，例如针对列表：
   [1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 44, 4, 5, 6, 1, 4, 5, 3, 6, 7, 8, 9, 11, 123, 22, 44, 1, 5, 5]
   得到出现次数统计：[(3, 10), (1, 4), (5, 4), (44, 2), (4, 2), (6, 2), (7, 1), (8, 1), (9, 1), (11, 1), (123, 1), (22, 1)]
2. 按出现次数分组处理重复元素：
   • 出现10次的元素3：分配在0到29位置，间隔约3个位置
   • 出现4次的元素1和5：分别分配在对应区间，间隔约6个位置
   • 出现2次的元素44、4、6：分配在指定的首尾对应位置
3. 用无重复元素填充剩余空位；若位置冲突，交替尝试±1、±2等步长，直到找到空闲位置。

实现代码 #

from collections import defaultdict

def find_nearest_none(arr, position):
    if arr[position] is None:
        return position

    step = 1
    while True:
        left_pos = position - step
        right_pos = position + step

        if left_pos >= 0 and arr[left_pos] is None:
            return left_pos
        elif right_pos < len(arr) and arr[right_pos] is None:
            return right_pos
        elif left_pos < 0 and right_pos >= len(arr):
            # Both left and right positions are out of bounds
            return False

        step += 1

def max_distance_list(nums):
    num_occurrences = {}
    t = len(nums)
    out = [None] * t
    
    for num in nums:
        num_occurrences[num] = num_occurrences.get(num, 0) + 1
    num_occurrences = sorted(num_occurrences.items(), key=lambda item: item[1], reverse=True)

    grouped_data = defaultdict(list)
    for key, value in num_occurrences:
        grouped_data[value].append(key)

    print(grouped_data)

    start_pos = 0 
    for x, y in dict(grouped_data).items():
        print("Start pos:", start_pos)
        for z in y:
            sep = t // x
            pos = start_pos;
            for i in range(x):
                free_pos = find_nearest_none(out, pos)
                out[free_pos] = z 
                pos+=sep;
            start_pos+=1;
    return out

现有输出结果 #

运行代码后得到：
[3, 1, 5, 3, 44, 4, 3, 6, 1, 3, 5, 7, 3, 8, 1, 3, 5, 44, 3, 4, 6, 3, 1, 5, 3, 9, 11, 3, 123, 22]

待解决问题 #

当前方案仅能满足基本需求，结果并非最优，且效率较低。询问是否存在现成的更优、更快的算法或函数可实现该需求。若没有合适方案，将分块使用当前方案，该需求用于构建爬虫队列，以分隔对同一IP或域名的请求。

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