数组中的最大组合差异，Python
Maximum combined difference in array, Python
问题
我得到了一个 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)))```
这似乎是个好主意。你会想要最大化每一个差异，所以你会从最高的开始，而不是通过放置两个最低的元素，而不是最高的等等来最大化那个差异。当我想到这个问题时，这似乎是最好的主意。尽管我认为我们不需要为 100 个元素出队。我会试试的！
我意识到我误读了你的问题，发现你已经想到了我在下面描述的方法（即交错最大和最小值，尝试将最小值和最大值都作为最内层的值）。所以无论如何，我将留下的只是我的实现和用于测试暴力破解的代码。测试代码表明这个“解决方案”基本上适用于所有情况，并且比蛮力方法快得多（但仍然存在证明问题）。
我的代码：
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}'
分析蛮力结果，我确定了一些我认为可以用来快速计算结果的价值顺序模式：
- 中间的值总是第一个（或镜像顺序中的最后一个）
- 对于奇数大小的列表，剩余元素的中间值总是最后一个
- 其余值（不包括第一个和奇数的最后一个）在排序元素的上半部分和下半部分之间交替，以上半部分或下半部分开始
- 上下半部分不是升序就是降序
根据这个观察（猜想），该函数将最多检查 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
虽然我没有正式的证明，但这似乎有效（而且速度非常快）。
由于您交替使用较大和较小的数字，因此每个交替位置的两个较大数字之间会有一个较小的数字。类似于 bignum smallnum bignum smallnum....。您可以轻松排列较大的数字，从中间的最大数字开始，然后将较小的数字向外扩展。
现在，所有较小数字的排列都会给出相同的结果。
假设当前的数字排列是a b c d e，其中递增顺序的数字是b < d < e < a < c。
- 当前差值：
(a-b) + (c-b) + (c-d) + (e-d) = a+e+(2*c)-(2*b)-(2*d)
- 让我们交换
b 和 d。现在序列变成 a d c b e。新的差异= (a-d) + (c-d) + (c-b) + (e-b) = a+e+(2*c)-(2*b)-(2*d)，与之前的差异相同。
- 尝试将
a 与 e 交换，也会得到相同的结果。
排列较大的数字是重要的部分，将较大的数字放在中间，因为它们对总差异的贡献是两倍。之后，可以按任意顺序插入较小的数字，因为这不会影响总差。
我处理问题的方式略有不同。
以这个列表为例：
[4, 1, 8, 2, 7, 3, 2, 4, 10, 3]
正如我目前所看到的其他解决方案以及您的@Kangaroo976，列表是这样排序的：
[4, 3, 7, 2, 10, 1, 8, 2, 4, 3]
[['LEFT'], ['LEFT'], ['LEFT'], ['LEFT'], ['MAX VAL'], ['RIGHT'], ['RIGHT'], ['RIGHT'], ['RIGHT'], ['RIGHT']]
相反，我以不同的方式描绘，所以基本上有 2 个 管道 ，它们是 2 个列表，交替具有最大和最小值，所以我的实现使用相同的输入列表，我会像这样将列表按 2 排序：
# MAX # MIN
|| 10 * 1 ||
|| 8 * 2 ||
|| 7 * 2 ||
|| 4 * 3 ||
|| 4 * 3 ||
然后你为每个数字计算每个 2 索引 2 次，因为你有组或 集群 如下：
# MAX # MIN
|| 10 * 1 || (10 -1) + (10-2) + (8-1) + (8-2)
|| 8 * 2 ||
|| 7 * 2 || (7-2) + (7-3) + (4-2) + (4-3)
|| 4 * 3 ||
|| 4 * 3 || (4-3)
如果列表中有 odds 个数字，例如 [4, 1, 8, 2, 7, 3, 2, 4, 10]，则计算略有不同：
# MAX # MIN
|| 10 * 1 || (10 -1) + (10-2) + (8-1) + (8-2)
|| 8 * 2 ||
|| 7 * 2 || (7-2) + (7-3) + (4-2) + (4-3)
|| 4 * 3 ||
|| * 4 || # Not Counted
第一个解决方案
注意，比你原来的要慢一点
def algorithm(input_list):
max_pipe = list()
min_pipe = list()
max_difference = 0
while len(input_list) > 1:
# --------------- Left Side Max Pipe
max_n = input_list.index(max(input_list))
max_pipe.append(input_list.pop(max_n))
# --------------- Right Side Min Pipe
min_n = input_list.index(min(input_list))
min_pipe.append(input_list.pop(min_n))
if input_list:
min_pipe.append(input_list.pop())
max_comparison = len(min_pipe) - 1
counter = 0 # NOTE: Counter reset each 4. Then adds +2 to offset
offset = 0
for max_val in range(max_comparison):
# --------------- Handle Clusters of calculations, which are each 4 steps
if counter == 4:
counter = 0
offset += 2
for comparison in range(2):
diff = max_pipe[max_val] - min_pipe[comparison + offset]
max_difference += diff
counter += 1
if len(min_pipe) % len(max_pipe) == 0: # NOTE: In list is uneven, needs a last comparison with both last values
max_difference += max_pipe[-1] - min_pipe[-1]
return max_difference
第二种解决方案
因此，按照这个逻辑，对列表进行排序，然后以 Divide-and-conquer 的方式划分列表，我想出了这个解决方案：
def algorithm(input_list):
max_difference = 0
# --------------- List Sorting & Setting Up Max And Min Pip
input_list.sort()
half = len(input_list)//2
max_pipe = input_list[half:]
min_pipe = input_list[:half]
# --------------- Loop Utils
total_comparison = len(input_list) - 2
counter = 1
offset = 0
# --------------- Algorithm
for n in range(half//2):
if counter == total_comparison: # The Algorithm can have only a certain and precise amount of calculations
break
comparison = 0
for N in max_pipe[-counter::-1]:
max_difference += N - min_pipe[offset*2]
max_difference += N - min_pipe[offset*2 + 1]
comparison += 1
if comparison == 2: # NOTE: Only 2 Comparison for each couple (Max, Min) num
break
counter += 2
offset += 1
max_difference += max_pipe[0] - min_pipe[-1] # Last calculation left over
return max_difference
基准测试
original = min(timeit.Timer(original_).repeat(1, 20))
print(mine)
print(original)
print('==='*15)
print(min(mine, original))
输出
5.1045565999999996 # Mine
5.519946699999999 # Kangaroo976
=============================================
5.1045565999999996
问题
我得到了一个 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)))```
这似乎是个好主意。你会想要最大化每一个差异，所以你会从最高的开始，而不是通过放置两个最低的元素，而不是最高的等等来最大化那个差异。当我想到这个问题时，这似乎是最好的主意。尽管我认为我们不需要为 100 个元素出队。我会试试的！
我意识到我误读了你的问题，发现你已经想到了我在下面描述的方法（即交错最大和最小值，尝试将最小值和最大值都作为最内层的值）。所以无论如何，我将留下的只是我的实现和用于测试暴力破解的代码。测试代码表明这个“解决方案”基本上适用于所有情况，并且比蛮力方法快得多（但仍然存在证明问题）。
我的代码：
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}'
分析蛮力结果，我确定了一些我认为可以用来快速计算结果的价值顺序模式：
- 中间的值总是第一个（或镜像顺序中的最后一个）
- 对于奇数大小的列表，剩余元素的中间值总是最后一个
- 其余值（不包括第一个和奇数的最后一个）在排序元素的上半部分和下半部分之间交替，以上半部分或下半部分开始
- 上下半部分不是升序就是降序
根据这个观察（猜想），该函数将最多检查 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
虽然我没有正式的证明，但这似乎有效（而且速度非常快）。
由于您交替使用较大和较小的数字，因此每个交替位置的两个较大数字之间会有一个较小的数字。类似于 bignum smallnum bignum smallnum....。您可以轻松排列较大的数字，从中间的最大数字开始，然后将较小的数字向外扩展。
现在，所有较小数字的排列都会给出相同的结果。
假设当前的数字排列是a b c d e，其中递增顺序的数字是b < d < e < a < c。
- 当前差值：
(a-b) + (c-b) + (c-d) + (e-d) = a+e+(2*c)-(2*b)-(2*d) - 让我们交换
b和d。现在序列变成a d c b e。新的差异=(a-d) + (c-d) + (c-b) + (e-b) = a+e+(2*c)-(2*b)-(2*d)，与之前的差异相同。 - 尝试将
a与e交换，也会得到相同的结果。
排列较大的数字是重要的部分，将较大的数字放在中间，因为它们对总差异的贡献是两倍。之后，可以按任意顺序插入较小的数字，因为这不会影响总差。
我处理问题的方式略有不同。
以这个列表为例：
[4, 1, 8, 2, 7, 3, 2, 4, 10, 3]
正如我目前所看到的其他解决方案以及您的@Kangaroo976，列表是这样排序的：
[4, 3, 7, 2, 10, 1, 8, 2, 4, 3]
[['LEFT'], ['LEFT'], ['LEFT'], ['LEFT'], ['MAX VAL'], ['RIGHT'], ['RIGHT'], ['RIGHT'], ['RIGHT'], ['RIGHT']]
相反，我以不同的方式描绘，所以基本上有 2 个 管道 ，它们是 2 个列表，交替具有最大和最小值，所以我的实现使用相同的输入列表，我会像这样将列表按 2 排序：
# MAX # MIN
|| 10 * 1 ||
|| 8 * 2 ||
|| 7 * 2 ||
|| 4 * 3 ||
|| 4 * 3 ||
然后你为每个数字计算每个 2 索引 2 次，因为你有组或 集群 如下：
# MAX # MIN
|| 10 * 1 || (10 -1) + (10-2) + (8-1) + (8-2)
|| 8 * 2 ||
|| 7 * 2 || (7-2) + (7-3) + (4-2) + (4-3)
|| 4 * 3 ||
|| 4 * 3 || (4-3)
如果列表中有 odds 个数字，例如 [4, 1, 8, 2, 7, 3, 2, 4, 10]，则计算略有不同：
# MAX # MIN
|| 10 * 1 || (10 -1) + (10-2) + (8-1) + (8-2)
|| 8 * 2 ||
|| 7 * 2 || (7-2) + (7-3) + (4-2) + (4-3)
|| 4 * 3 ||
|| * 4 || # Not Counted
第一个解决方案
注意，比你原来的要慢一点
def algorithm(input_list):
max_pipe = list()
min_pipe = list()
max_difference = 0
while len(input_list) > 1:
# --------------- Left Side Max Pipe
max_n = input_list.index(max(input_list))
max_pipe.append(input_list.pop(max_n))
# --------------- Right Side Min Pipe
min_n = input_list.index(min(input_list))
min_pipe.append(input_list.pop(min_n))
if input_list:
min_pipe.append(input_list.pop())
max_comparison = len(min_pipe) - 1
counter = 0 # NOTE: Counter reset each 4. Then adds +2 to offset
offset = 0
for max_val in range(max_comparison):
# --------------- Handle Clusters of calculations, which are each 4 steps
if counter == 4:
counter = 0
offset += 2
for comparison in range(2):
diff = max_pipe[max_val] - min_pipe[comparison + offset]
max_difference += diff
counter += 1
if len(min_pipe) % len(max_pipe) == 0: # NOTE: In list is uneven, needs a last comparison with both last values
max_difference += max_pipe[-1] - min_pipe[-1]
return max_difference
第二种解决方案
因此，按照这个逻辑，对列表进行排序，然后以 Divide-and-conquer 的方式划分列表，我想出了这个解决方案：
def algorithm(input_list):
max_difference = 0
# --------------- List Sorting & Setting Up Max And Min Pip
input_list.sort()
half = len(input_list)//2
max_pipe = input_list[half:]
min_pipe = input_list[:half]
# --------------- Loop Utils
total_comparison = len(input_list) - 2
counter = 1
offset = 0
# --------------- Algorithm
for n in range(half//2):
if counter == total_comparison: # The Algorithm can have only a certain and precise amount of calculations
break
comparison = 0
for N in max_pipe[-counter::-1]:
max_difference += N - min_pipe[offset*2]
max_difference += N - min_pipe[offset*2 + 1]
comparison += 1
if comparison == 2: # NOTE: Only 2 Comparison for each couple (Max, Min) num
break
counter += 2
offset += 1
max_difference += max_pipe[0] - min_pipe[-1] # Last calculation left over
return max_difference
基准测试
original = min(timeit.Timer(original_).repeat(1, 20))
print(mine)
print(original)
print('==='*15)
print(min(mine, original))
输出
5.1045565999999996 # Mine
5.519946699999999 # Kangaroo976
=============================================
5.1045565999999996