数组中的最大组合差
数组中的最大组合差
提问于 2021-01-05 14:51:25
问题
给出了一个n <= 100正整数序列。如何通过重新排列数组中的元素，在可以达到的元素之间找到最大可能的组合差异？
例如，对于序列{8、4、1、2、3}，起始差是(8-4) + (4-1) + (2-1) + (3-2) = 9，但是对于{4、8、1、3、2}可以达到14。
最佳排列为{4，1，8，2，3}。预期的答案将是可以达到的最大值，因此在本例中为17。
我的方法
- I会对数组进行排序，然后生成一个Python
collections.deque()，将最小元素和最大元素交替添加到两个元素中；这有意义吗？
- 这种天真的方法不正确吗？
- 我们可以尝试两种情况，从最小元素和最大元素开始。
排列的数目可以达到100！所以没有畜生会这么做。
一些代码
input_data = [int(x) for x in input().split(" ")]
input_data.sort()
def maximum_difference_sort(data: list, *, start_with_max):
queue = deque()
indices = [0, -1] if start_with_max else [-1, 0]
queue.append(data.pop(indices[1]))
while True:
try:
queue.append(data.pop(indices[0]))
queue.appendleft(data.pop(indices[0]))
queue.append(data.pop(indices[1]))
queue.appendleft(data.pop(indices[1]))
except IndexError:
break
return list(queue)
def combined_difference(seq):
s = 0
for i in range(1, len(seq)):
s += abs(seq[i] - seq[i-1])
return s
print(combined_difference(maximum_difference_sort(input_data, start_with_max=True)))```回答 3
Stack Overflow用户
发布于 2021-01-05 20:31:18
通过对蛮力结果的分析，我确定了几种价值顺序模式，我认为这些模式可以用来快速计算结果：
- 中间值始终是奇数大小列表的第一个(或镜像顺序中的最后一个)
- ，其余元素的中间值总是最后一个
- 剩余值(不包括第一个和最后一个)在排序元素的上半部分和下半部分之间交替，上半段或下半段
- ，上半段和下半部的
根据这一观察(猜想)，该函数最多需要检查8种模式：
def sumDiffs(R): return sum(abs(a-b) for a,b in zip(R,R[1:]))
def maxDiffs(A):
if len(A)<=2 : return sumDiffs(A),A
S = sorted(A)
first = [S.pop(len(S)//2)]
half = len(S)//2
lower = S[:half]
upper = S[-half:]
last = S[half:-half]
def interlace(L,R): return [n for ab in zip(L,R) for n in ab]
patterns = []
for L,R in [(lower,upper),(upper,lower)]:
for ld,rd in [(1,1),(1,-1),(-1,1),(-1,-1)]:
patterns.append(first + interlace(L[::ld],R[::rd]) + last)
return max( (sumDiffs(p),p) for p in patterns )
print(*maxDiffs([8, 4, 1, 2, 3])) # 17 [3, 1, 8, 2, 4]
print(*maxDiffs([8, 4, 1, 2, 3, 7])) # 25 [4, 1, 8, 2, 7, 3]为了验证这一点，我将结果与随机生成的各种大小的列表中的蛮力函数进行了比较：
from itertools import permutations
def bruteForce(A):
return max( (sumDiffs(P),P) for P in permutations(A) )
import random
for size in range(1,101):
failedCount = 0
for i in range(10):
A = list(random.randrange(size*size) for _ in range(size))
bfSum,bfValues = bruteForce(A)
maxSum,values = maxDiffs(A)
if maxSum!=bfSum:
print(size,"failed:",bfSum,maxSum,bfValues,values)
failedCount += 1
print("size",size,"failed:",failedCount)
size 1 failed: 0
size 2 failed: 0
size 3 failed: 0
size 4 failed: 0
size 5 failed: 0
size 6 failed: 0
size 7 failed: 0
size 8 failed: 0
size 9 failed: 0
size 10 failed: 0
size 11 failed: 0虽然我没有正式的证据，但这似乎有效(而且速度很快)。
Stack Overflow用户
发布于 2021-01-05 15:05:32
这似乎是个好主意。您会希望最大限度地扩大每一个差异，所以您将从最高开始，而不是最大限度地扩大这种差异，将两个最低的元素，而不是最高的，等等。当我想到这个问题的时候，这似乎是最好的主意。即使我不认为我们需要排100元素。我试试看！
Stack Overflow用户
发布于 2021-01-05 17:22:10
我意识到我误解了您的问题，并且看到您已经设想了我下面描述的方法(即将最大值和最小值交织在一起，尝试将最小值和最大值作为最内部的值)。所以在任何情况下，我要留下的就是我的实现和针对蛮力的测试代码。测试代码显示，这种“解决方案”基本上适用于所有情况，并且比蛮力方法快得多(但仍然存在证据问题)。
我的代码：
def little_big_sort(l):
s = sorted(l)
result = []
result.append(s.pop(0))
while len(s):
if s:
result.insert(len(result), s.pop(-1))
if s:
result.insert(0, s.pop(-1))
if s:
result.insert(len(result), s.pop(0))
if s:
result.insert(0, s.pop(0))
return result
def big_little_sort(l):
s = sorted(l)
result = []
result.append(s.pop())
while len(s):
if s:
result.insert(len(result), s.pop(0))
if s:
result.insert(0, s.pop(0))
if s:
result.insert(len(result), s.pop(-1))
if s:
result.insert(0, s.pop(-1))
return result
def diff_sum(l):
result = 0
for i in range(len(l[:-1])):
result += abs(l[i] - l[i+1])
return result
def solution(l):
return max(diff_sum(little_big_sort(l)), diff_sum(big_little_sort(l)))蛮力办法：
def brute_force(l):
result = 0
for i in itertools.permutations(l):
if diff_sum(i) > result:
result = diff_sum(i)
return result至于测试：
import random
n = 2 # items in list
m = 10000 # repetitions
lo = 0
hi = 100
cases = [random.sample(range(lo, hi),n) for i in range(m)]
for i in cases:
assert brute_force(i) == solution(i), f'failure for case {i}'页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65581190
复制相关文章
相似问题
腾讯云开发者
