I'm interested in reordering a list in such a manner as to maximize the sum of the squares of the differences between adjacent elements (cyclic). Here is a piece of Python code that brute-forces the solution in factorial time, so you can see what I mean:
我感兴趣的是重新排序一个列表，以便最大化相邻元素(循环)之间差异的平方和。下面是一段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
This yields the following results for maximal_difference_reorder(range(4)):
这就产生了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)]
As you can see, all the results are cyclic rotations and reflections of each other. If the score was determined with the sum of the differences, not squared, I believe all permutations would be evenly scored, given an evenly-spaced input.
正如你所看到的，所有的结果都是循环旋转和彼此的反射。如果分数是用差异的和来决定的，而不是平方，我相信所有的排列都会被平均地打分，给定一个均匀间隔的输入。
Brute forcing works well, but O(n!) is terrible, so is it possible to do this in a smaller asymptotic computational time? Bonus points if it works for an uneven input mesh, or for other scoring functions.
蛮力处理得很好，但是O(n!)很糟糕，那么在一个更小的渐近计算时间内做这个有可能吗?如果它适用于不均匀的输入网格，或者其他的得分函数。
Incidentally, this isn't homework or an interview question, though perhaps it would make a good one. Rather, I'm trying to generate a spectrum of colours for a series of parameterised data, and I'm trying to avoid having similar colours next to each other.
顺便说一句，这不是家庭作业或面试问题，尽管这可能是个好问题。相反，我试图为一系列参数化的数据生成一个颜色谱，并且我试图避免相邻的颜色相似。
4 个解决方案
#1
3
Your problem is a slightly disguised instance of the Traveling Salesman Problem.
你的问题是旅行推销员问题的一个稍微掩饰的例子。
Call the input list c (for "cities"). Pick any M which is an upper bound on (c[i]-c[j])**2 This is easily done in linear time since the min and the max of the list can be computed in a single pass, in which case M = (max - min)**2 works. Define the distance, d[i,j] from c[i] to c[j] by:
调用输入列表c(表示“城市”)。在线性时间内，可以很容易地完成这一操作，因为列表中的最小值和最大值都可以在一个通道中计算，在这种情况下，M = (max - min)**2工作。定义距离，d[i,j]从c[i]到c[j]的距离，由:
d(i,j) = 0 if i == j else M - (c[i]-c[j])**2
It is easy to see that for any cyclic permutation the cost of that permutation (computed according to d) is n*M - sum of squares of differences hence it is minimized if and only the sum of the squares of the differences is maximized.
很容易看出，对于任何循环排列，该排列(根据d计算)的代价是n*M -差异平方和，因此，当且仅是差异的平方和被最大化时，它被最小化。
There are a wealth of approaches to solving a TSP. Even though it is NP-hard, in practice state-of-the art methods are phenomenally good at solving problems that arise in practice. Furthermore, good heuristic methods can typically get to within a fraction of a percent of optimal.
解决TSP有很多方法。尽管它是np困难的，但在实践中，先进的方法在解决实践中出现的问题上表现得非常出色。此外，好的启发式方法通常可以达到百分之一的最佳值。
Your particular problem is a special case of a TSP. As such it is possible that this special case is easier and in fact has a polynomial time solution, but I doubt it. I conjecture that it is NP-hard as well but don't have a proof. Also -- even if it is NP-hard, it might be that there is a solution (perhaps an Integer Programming formulation) which is more efficient than reducing it to TSP as above.
你的问题是TSP的一个特例。因此，这种特殊情况可能更容易，而且实际上有一个多项式时间解，但我对此表示怀疑。我猜想它也是NP-hard，但没有证据。而且——即使它是np困难的，也可能有一个解决方案(可能是整数编程公式)比将它减少到TSP更有效。
On Edit: based on comments by Dave Gavin and the answer by @SergeBallesta I now think that a polynomial time algorithm is possible. I'll leave this answer up, if for no other reason than if a polynomial time algorithm works then this problem would be a nice example for showing that certain subclasses of the TSP have simpler solutions.
关于编辑:根据Dave Gavin的评论和@SergeBallesta的答案，我现在认为一个多项式时间算法是可能的。我就不回答这个问题了，如果只是因为多项式时间算法有效，那么这个问题就是一个很好的例子来说明TSP的某些子类有更简单的解。
#2
2
If you are trying to maximize the squares of the differences between consecutive elements in a cyclic way, I would say that you should try to have the biggest element near to the smallest because conceptually a²+b²>=2*((a+b)/2)². That's what you have found by brute force with range(4).
如果你想最大化之间的差异的广场连续元素循环的方式,我认为你应该尽量最大的元素接近最小的,因为概念上²+ b²> = 2 *((a + b)/ 2)²。这就是你在使用range(4)的蛮力时发现的。
I think that it could be shown by induction, but that part should be better asked on Mathematics but I would bet a coin that the solution is simply to:
我认为它可以用归纳法来表示，但这部分应该用数学来表示，但我敢打赌，答案很简单:
- sort the list
- 排序的列表
- take biggest element put it in index 0 of result list
- 取最大元素，将其放入结果列表的索引0中
- take smallest one and put it on index 1
- 取最小的一个，放到索引1上。
- take smallest of remaining and put it on index -1
- 取剩下的最小值，然后把它放到index -1上。
- take biggest of remaining and put it on index 2
- 取最大的余数，放到指数2上
and iterate one time to the right and one to the left alternating biggest and smallest of remaining elements
然后向右迭代1次，向左迭代1次
You end in:
你结束:
- O(n * log(n)) statistic for the sort with quicksort or merge-sort, or O(n²/2) with a mere bubble sort
- O(n * log(n))统计排序和快速排序或合并排序,或O(n²/ 2)仅仅是冒泡排序
- linear for building the result array
- 线性用于构建结果数组
#3
1
I think we can have an O(n) solution
我想我们可以有一个O(n)解
The key to solve this problem is to generate the first seed for the cyclic group. Considering we should be pairing the elements wherein the pairwise square difference sum is maximum which is possible if we pair an element with its farthest neighbor.
解决这个问题的关键是为循环组生成第一个种子。考虑到我们应该对元素进行配对，其中两两平方和是最大的，这是可能的，如果我们把一个元素和它的最远邻居配对。
Which means if hi is the ith highest number, then the neighbors of hi are (hn-i-1, hn-i+1). As the sequence is cyclic so the numbers would wrap around for negative index i.e. h-1 = h0 This will generate the first seed list as [0, 6, 2, 4, 3, 5, 1, 7]
这意味着如果hi是第i个最高的数字，那么hi的邻居是(hn-i-1, hn-i+1)。由于序列是循环的，所以这些数字会围绕着负数指数，即h-1 = h0这将产生第一个种子列表为[0,6,2,4,3,5,1,7]
This sequence can easily be generating by swapping every odd index pair i.e. [(a1, an-1), (a3, an-3),...]
这个序列可以通过交换每个奇数索引对来生成，例如[(a1, an-1)， (a3, an-3)，…]
The subsequent sequence can be generated by generating a singular sequential rotation and then reflecting the rotated sequence
通过生成一个奇异的顺序旋转，然后反射旋转的序列，可以生成后续序列
Here is a sample implementation
下面是一个示例实现
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)
Sample Run
样本运行
def display(lst, width = 80):
it_lst = iter(lst)
try:
print '[',
while True:
for _ in range(80/(len(lst[0])*3 + 2)):
print "{},".format(next(it_lst)),
print '\n ',
except StopIteration:
print ']'
display(maximal_difference_reorder1(range(10)))
[ (0, 8, 2, 6, 4, 5, 3, 7, 1, 9), (8, 2, 6, 4, 5, 3, 7, 1, 9, 0),
(2, 6, 4, 5, 3, 7, 1, 9, 0, 8), (6, 4, 5, 3, 7, 1, 9, 0, 8, 2),
(4, 5, 3, 7, 1, 9, 0, 8, 2, 6), (5, 3, 7, 1, 9, 0, 8, 2, 6, 4),
(3, 7, 1, 9, 0, 8, 2, 6, 4, 5), (7, 1, 9, 0, 8, 2, 6, 4, 5, 3),
(1, 9, 0, 8, 2, 6, 4, 5, 3, 7), (9, 0, 8, 2, 6, 4, 5, 3, 7, 1),
(9, 1, 7, 3, 5, 4, 6, 2, 8, 0), (0, 9, 1, 7, 3, 5, 4, 6, 2, 8),
(8, 0, 9, 1, 7, 3, 5, 4, 6, 2), (2, 8, 0, 9, 1, 7, 3, 5, 4, 6),
(6, 2, 8, 0, 9, 1, 7, 3, 5, 4), (4, 6, 2, 8, 0, 9, 1, 7, 3, 5),
(5, 4, 6, 2, 8, 0, 9, 1, 7, 3), (3, 5, 4, 6, 2, 8, 0, 9, 1, 7),
(7, 3, 5, 4, 6, 2, 8, 0, 9, 1), (1, 7, 3, 5, 4, 6, 2, 8, 0, 9),
]
Note It is assumed that the data is sorted. If not, it is trivial to sort it wherein the solution complexity would be O(nlog n)
注意，假定数据已排序。如果不是，那么排序是很简单的，其中解决方案的复杂性是O(nlog n)
#4
1
Here's the greedy algorithm I suggested in the comments:
下面是我在评论中建议的贪婪算法:
How about the greedy algorithm? At each step, prepend or append the number to increase the score the most (this will make a zigzag wave of increasing then decreasing amplitude). Try that starting with either the smallest number or largest number
那么贪婪算法呢?在每个步骤中，prepend或附加该数字以增加得分最多(这将使一个锯齿波增加，然后减小振幅)。尝试从最小或最大的数开始
It would be interesting to study example where greedy algorithm is not optimal
研究贪心算法不是最优的例子是很有趣的
# https://*.com/questions/34154324/reordering-a-list-to-maximize-difference-of-adjacent-elements?s=2|0.0000
import itertools
def score(x):
return sum((a-b)**2 for a,b in zip(x, x[1:]))
assert score([0, 2, 5]) == 4 + 9
def maximise(x):
x = sorted(x)
candidates = [greedy(x[:1], x[1:]), greedy(x[-1:], x[:-1])]
return max(candidates, key=score)
def greedy(current, remaining):
while remaining:
i, j = max(itertools.product((0, -1), repeat=2), key=lambda pair: score((current[pair[0]], remaining[pair[1]])))
current.insert(i, remaining.pop(j))
return current
def cyclic_score(x):
return sum((a-b)**2 for a,b in zip(x, x[1:] + x[:1]))
assert cyclic_score([0, 2, 5]) == 4 + 9 + 25
#1
3
Your problem is a slightly disguised instance of the Traveling Salesman Problem.
你的问题是旅行推销员问题的一个稍微掩饰的例子。
Call the input list c (for "cities"). Pick any M which is an upper bound on (c[i]-c[j])**2 This is easily done in linear time since the min and the max of the list can be computed in a single pass, in which case M = (max - min)**2 works. Define the distance, d[i,j] from c[i] to c[j] by:
调用输入列表c(表示“城市”)。在线性时间内，可以很容易地完成这一操作，因为列表中的最小值和最大值都可以在一个通道中计算，在这种情况下，M = (max - min)**2工作。定义距离，d[i,j]从c[i]到c[j]的距离，由:
d(i,j) = 0 if i == j else M - (c[i]-c[j])**2
It is easy to see that for any cyclic permutation the cost of that permutation (computed according to d) is n*M - sum of squares of differences hence it is minimized if and only the sum of the squares of the differences is maximized.
很容易看出，对于任何循环排列，该排列(根据d计算)的代价是n*M -差异平方和，因此，当且仅是差异的平方和被最大化时，它被最小化。
There are a wealth of approaches to solving a TSP. Even though it is NP-hard, in practice state-of-the art methods are phenomenally good at solving problems that arise in practice. Furthermore, good heuristic methods can typically get to within a fraction of a percent of optimal.
解决TSP有很多方法。尽管它是np困难的，但在实践中，先进的方法在解决实践中出现的问题上表现得非常出色。此外，好的启发式方法通常可以达到百分之一的最佳值。
Your particular problem is a special case of a TSP. As such it is possible that this special case is easier and in fact has a polynomial time solution, but I doubt it. I conjecture that it is NP-hard as well but don't have a proof. Also -- even if it is NP-hard, it might be that there is a solution (perhaps an Integer Programming formulation) which is more efficient than reducing it to TSP as above.
你的问题是TSP的一个特例。因此，这种特殊情况可能更容易，而且实际上有一个多项式时间解，但我对此表示怀疑。我猜想它也是NP-hard，但没有证据。而且——即使它是np困难的，也可能有一个解决方案(可能是整数编程公式)比将它减少到TSP更有效。
On Edit: based on comments by Dave Gavin and the answer by @SergeBallesta I now think that a polynomial time algorithm is possible. I'll leave this answer up, if for no other reason than if a polynomial time algorithm works then this problem would be a nice example for showing that certain subclasses of the TSP have simpler solutions.
关于编辑:根据Dave Gavin的评论和@SergeBallesta的答案，我现在认为一个多项式时间算法是可能的。我就不回答这个问题了，如果只是因为多项式时间算法有效，那么这个问题就是一个很好的例子来说明TSP的某些子类有更简单的解。
#2
2
If you are trying to maximize the squares of the differences between consecutive elements in a cyclic way, I would say that you should try to have the biggest element near to the smallest because conceptually a²+b²>=2*((a+b)/2)². That's what you have found by brute force with range(4).
如果你想最大化之间的差异的广场连续元素循环的方式,我认为你应该尽量最大的元素接近最小的,因为概念上²+ b²> = 2 *((a + b)/ 2)²。这就是你在使用range(4)的蛮力时发现的。
I think that it could be shown by induction, but that part should be better asked on Mathematics but I would bet a coin that the solution is simply to:
我认为它可以用归纳法来表示，但这部分应该用数学来表示，但我敢打赌，答案很简单:
- sort the list
- 排序的列表
- take biggest element put it in index 0 of result list
- 取最大元素，将其放入结果列表的索引0中
- take smallest one and put it on index 1
- 取最小的一个，放到索引1上。
- take smallest of remaining and put it on index -1
- 取剩下的最小值，然后把它放到index -1上。
- take biggest of remaining and put it on index 2
- 取最大的余数，放到指数2上
and iterate one time to the right and one to the left alternating biggest and smallest of remaining elements
然后向右迭代1次，向左迭代1次
You end in:
你结束:
- O(n * log(n)) statistic for the sort with quicksort or merge-sort, or O(n²/2) with a mere bubble sort
- O(n * log(n))统计排序和快速排序或合并排序,或O(n²/ 2)仅仅是冒泡排序
- linear for building the result array
- 线性用于构建结果数组
#3
1
I think we can have an O(n) solution
我想我们可以有一个O(n)解
The key to solve this problem is to generate the first seed for the cyclic group. Considering we should be pairing the elements wherein the pairwise square difference sum is maximum which is possible if we pair an element with its farthest neighbor.
解决这个问题的关键是为循环组生成第一个种子。考虑到我们应该对元素进行配对，其中两两平方和是最大的，这是可能的，如果我们把一个元素和它的最远邻居配对。
Which means if hi is the ith highest number, then the neighbors of hi are (hn-i-1, hn-i+1). As the sequence is cyclic so the numbers would wrap around for negative index i.e. h-1 = h0 This will generate the first seed list as [0, 6, 2, 4, 3, 5, 1, 7]
这意味着如果hi是第i个最高的数字，那么hi的邻居是(hn-i-1, hn-i+1)。由于序列是循环的，所以这些数字会围绕着负数指数，即h-1 = h0这将产生第一个种子列表为[0,6,2,4,3,5,1,7]
This sequence can easily be generating by swapping every odd index pair i.e. [(a1, an-1), (a3, an-3),...]
这个序列可以通过交换每个奇数索引对来生成，例如[(a1, an-1)， (a3, an-3)，…]
The subsequent sequence can be generated by generating a singular sequential rotation and then reflecting the rotated sequence
通过生成一个奇异的顺序旋转，然后反射旋转的序列，可以生成后续序列
Here is a sample implementation
下面是一个示例实现
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)
Sample Run
样本运行
def display(lst, width = 80):
it_lst = iter(lst)
try:
print '[',
while True:
for _ in range(80/(len(lst[0])*3 + 2)):
print "{},".format(next(it_lst)),
print '\n ',
except StopIteration:
print ']'
display(maximal_difference_reorder1(range(10)))
[ (0, 8, 2, 6, 4, 5, 3, 7, 1, 9), (8, 2, 6, 4, 5, 3, 7, 1, 9, 0),
(2, 6, 4, 5, 3, 7, 1, 9, 0, 8), (6, 4, 5, 3, 7, 1, 9, 0, 8, 2),
(4, 5, 3, 7, 1, 9, 0, 8, 2, 6), (5, 3, 7, 1, 9, 0, 8, 2, 6, 4),
(3, 7, 1, 9, 0, 8, 2, 6, 4, 5), (7, 1, 9, 0, 8, 2, 6, 4, 5, 3),
(1, 9, 0, 8, 2, 6, 4, 5, 3, 7), (9, 0, 8, 2, 6, 4, 5, 3, 7, 1),
(9, 1, 7, 3, 5, 4, 6, 2, 8, 0), (0, 9, 1, 7, 3, 5, 4, 6, 2, 8),
(8, 0, 9, 1, 7, 3, 5, 4, 6, 2), (2, 8, 0, 9, 1, 7, 3, 5, 4, 6),
(6, 2, 8, 0, 9, 1, 7, 3, 5, 4), (4, 6, 2, 8, 0, 9, 1, 7, 3, 5),
(5, 4, 6, 2, 8, 0, 9, 1, 7, 3), (3, 5, 4, 6, 2, 8, 0, 9, 1, 7),
(7, 3, 5, 4, 6, 2, 8, 0, 9, 1), (1, 7, 3, 5, 4, 6, 2, 8, 0, 9),
]
Note It is assumed that the data is sorted. If not, it is trivial to sort it wherein the solution complexity would be O(nlog n)
注意，假定数据已排序。如果不是，那么排序是很简单的，其中解决方案的复杂性是O(nlog n)
#4
1
Here's the greedy algorithm I suggested in the comments:
下面是我在评论中建议的贪婪算法:
How about the greedy algorithm? At each step, prepend or append the number to increase the score the most (this will make a zigzag wave of increasing then decreasing amplitude). Try that starting with either the smallest number or largest number
那么贪婪算法呢?在每个步骤中，prepend或附加该数字以增加得分最多(这将使一个锯齿波增加，然后减小振幅)。尝试从最小或最大的数开始
It would be interesting to study example where greedy algorithm is not optimal
研究贪心算法不是最优的例子是很有趣的
# https://*.com/questions/34154324/reordering-a-list-to-maximize-difference-of-adjacent-elements?s=2|0.0000
import itertools
def score(x):
return sum((a-b)**2 for a,b in zip(x, x[1:]))
assert score([0, 2, 5]) == 4 + 9
def maximise(x):
x = sorted(x)
candidates = [greedy(x[:1], x[1:]), greedy(x[-1:], x[:-1])]
return max(candidates, key=score)
def greedy(current, remaining):
while remaining:
i, j = max(itertools.product((0, -1), repeat=2), key=lambda pair: score((current[pair[0]], remaining[pair[1]])))
current.insert(i, remaining.pop(j))
return current
def cyclic_score(x):
return sum((a-b)**2 for a,b in zip(x, x[1:] + x[:1]))
assert cyclic_score([0, 2, 5]) == 4 + 9 + 25