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

我有兴趣以这样的方式重新排序列表,以便最大化相邻元素之间差异的平方和(循环).这是一段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)):

[(0, 2, 1, 3),
 (0, 3, 1, 2),
 (1, 2, 0, 3),
 (1, 3, 0, 2),
 (2, 0, 3, 1),
 (2, 1, 3, 0),
 (3, 0, 2, 1),
 (3, 1, 2, 0)]

如您所见,所有结果都是循环旋转和彼此反射.如果得分是用差值之和确定的,而不是平方,我相信所有排列都会得到均匀的评分,给出均匀间隔的输入.

暴力强迫效果很好,但O(n!)很糟糕,所以可以在较小的渐近计算时间内完成吗？如果它适用于不均匀的输入网格或其他评分函数,则可获得奖励积分.

顺便说一句,这不是家庭作业或面试问题,但也许它会成为一个好问题.相反,我正在尝试为一系列参数化数据生成一系列颜色,并且我试图避免彼此相邻的颜色相似.