如何创建一种算法来对给定半径的列表进行重新排序，确保重新排序后半径 r 内的元素不会保持紧密相邻

Question

我一直在努力解决这个问题，我需要创建一个算法来处理数组和给定的半径 r。该算法应重新排列元素，使索引 I 处的每个元素不在先前或后续元素的半径内。

例如数组 [1, 2, 3, 4, 5, 6]，其中 r= 2 对于索引 0 上的元素 1，它不能在 2 或 3 的范围内 对于索引 1 上的元素 2，它不能在 1、3 或 4 的范围内 对于索引 2 上的元素 3，它不能在 1、2、4 或 5 的范围内 等等...

如果这是不可能的，则返回包含最多满足条件的元素的数组

我怎样才能有效地解决这个问题？

我试图找到类似的leetcode问题，试图在这里、reddit和youtube上找到类似的帖子。但没有运气。

我知道你可能会为此制定一个强力算法，但这确实效率低下且缓慢。

Answer 1

我不确定这是否是最佳的，但这似乎适合我尝试过的输入。对列表进行切片，将每个第 n 个元素作为输出数组的同一连续“块”的一部分，其中

n = radius + 1

。然后通过减少交错/偏移来排序这些块。

def reorder(elems, radius):
    output = []
    for offset in range(radius, -1, -1):
        output.extend(elems[offset::radius+1])
    return output

当列表长度为半径的两倍或更长时，上述算法一定会返回最优结果。

稍后我会再多考虑一下，看看是否可以证明/反驳它的整体最优性。