重新排序列表以最大化相邻元素的差异

Question

我有兴趣以这样一种方式重新排序一个列表，以使相邻元素之间的差异平方和最大化（循环）。下面是一段Python代码，它在阶乘时间内强制执行解决方案，因此您可以看到我的意思：

def maximal_difference_reorder(input):

   from itertools import permutations

   best_sum = 0
   best_orderings = []

   for x in permutations(input):
        d = np.sum(np.diff(x)**2) + (x[0] - x[-1])**2
        if d > best_sum:
            best_orderings = [x]
            best_sum = d
        elif d == best_sum:
            best_orderings.append(x)

   return best_orderings

这将产生maximal_difference_reorder(range(4))的以下结果：

^{pr2}$

如您所见，所有结果都是循环旋转和相互反射。如果分数是用差的和而不是平方来决定的，我相信所有的排列都会得到平均的分数，只要输入一个均匀的间隔。在

暴力强制很有效，但是O（n！）是可怕的，那么有可能在更小的渐近计算时间内完成这项工作吗？加分，如果它适用于不均匀的输入网格，或其他评分功能。在

顺便说一句，这不是家庭作业或面试问题，虽然它可能是一个好问题。相反，我试图为一系列参数化的数据生成一个颜色光谱，并且我试图避免相邻的颜色相似。在

Answer 1

如果您试图以循环的方式最大化连续元素之间差异的平方，我会说您应该尝试让最大的元素接近最小的元素，因为概念上{}。这就是你所发现的暴力与range(4)。在

我认为可以用归纳法来说明，但这一部分最好是在Mathematics上提出的，但我敢打赌，解决办法很简单：

• 对列表排序
• 取最大的元素放入结果列表的索引0
• 取最小的那个放在索引1上
• 取剩下的最小值，放到索引-1上
• 取剩下的最大值，放在索引2上

然后向右和向左迭代一次剩余元素的最大和最小值

你的结局是：

• O（n*log（n））统计，用于快速排序或合并排序，或O（n²/2）仅用于冒泡排序
• 用于生成结果数组的线性

Answer 2

您的问题是一个稍微伪装的Traveling Salesman Problem实例。在

调用输入列表c（对于“城市”）。选择任何一个M，它是(c[i]-c[j])**2的上限，这很容易在线性时间内完成，因为列表的最小值和最大值可以在一个过程中计算出来，在这种情况下，M = (max - min)**2可以工作。定义距离，d[i,j]从c[i]到{}，方法如下：

d(i,j) = 0 if i == j else M - (c[i]-c[j])**2

很容易看出，对于任何循环置换，该置换的成本（根据d计算）是n*M - sum of squares of differences，因此当且仅当差分的平方和最大化时，它是最小的。在

有很多方法可以解决TSP。即使在实践中出现的NP问题也很难解决。此外，好的启发式方法通常可以达到最优值的百分之一。在

您的特殊问题是TSP的特殊情况。因此，这个特殊情况可能更容易，事实上有一个多项式时间解，但我对此表示怀疑。我猜想它也是NP难的，但没有证据。而且——即使它是NP难的，也可能有一个解决方案（也许是一个整数规划公式）比把它简化为TSP更有效。在

编辑：根据Dave Gavin的评论和@SergeBallesta的回答，我现在认为多项式时间算法是可能的。我把这个问题的答案留着，如果不是因为多项式时间算法起作用，那么这个问题将是一个很好的例子来说明TSP的某些子类有更简单的解决方案。在

Answer 3

我想我们可以有一个O（n）解决方案

解决这个问题的关键是生成循环群的第一种子。考虑到我们应该配对的元素，其中成对平方差和是最大的，这是可能的，如果我们配对一个元素与其最远的邻居。在

也就是说，如果h_i是i^th的最高数，那么h_i的邻居是（h_n-i-1，h_n-i+1）。由于序列是循环的，因此数字将环绕负指数，即h_-1=h₀ 这将生成第一个种子列表[0, 6, 2, 4, 3, 5, 1, 7]

通过交换每个奇数索引对，即[a₁，a_n-1），（a₃，a_n-3），…]

随后的序列可以通过产生一个奇异的序列旋转，然后反射旋转序列来生成

下面是一个示例实现

def maximal_difference_reorder1(x):
    def maximal_difference_seeder(x):
        for i in range(1, len(x) / 2):
            x[i:len(x) - i] = x[i:len(x) - i][::-1]
        return x
    def rotate_left(x):
        start = x
        while True:
            x = x[1:] + x[0:1]
            if x == start: break
            yield x

    x = maximal_difference_seeder(x)
    rotated = [x] + (list(rotate_left(x)) if len(x) > 1 else [])
    reflected = [e[::-1] for e in rotated] if len(x) > 2 else []
    return map(tuple, rotated + reflected)  

样本运行

^{pr2}$

注假设数据已排序。如果不是，那么对它进行排序是很简单的，其中解决方案的复杂性将是O（nlog n）