python - 数组中的最大组合差异，Python

Question

问题
我得到一个序列 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。
我的方法

我会对数组进行排序，然后创建一个 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)))```

Answer 1

在分析蛮力结果时，我确定了一些我认为可以用来快速计算结果的值(value)顺序模式:

中间值始终是第一个(或镜像顺序中的最后一个)

对于奇数大小的列表，剩余元素的中间值总是最后

剩余的值(不包括第一个和奇数的最后一个)在排序元素的上半部分和下半部分之间交替，以上半部分或下半部分开始

上下半部分按升序或降序排列

基于这个观察(猜想)，该函数最多有 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

虽然我没有正式的证明，但这似乎有效(而且速度非常快)。