Maximum combined difference in array, Python

Question

Problem

I am given a sequence of n <= 100 positive integers. How to find a maximum possible combined difference between the elements that can be reached by rearranging the elements in the array?

For example, for a sequence {8, 4, 1, 2, 3} the starting difference is (8-4) + (4-1) + (2-1) + (3-2) = 9, but 14 can be reached for {4, 8, 1, 3, 2}.

The best arrangement is {4, 1, 8, 2, 3}. The expected answer would be the maximum that can be reached, so in this case 17.

My approach

• I would sort the array and then make a Python collections.deque() to append to both sides smallest and largest elements alternately; would this make any sense?

• Is this naive approach incorrect?

• We can try two cases, starting with the smallest and the largest element.

The number of permutations can reach 100! so no brute will do that.

Some code

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

I handle the problem in a slightly different way.

Take for instance this list:

[4, 1, 8, 2, 7, 3, 2, 4, 10, 3]

As I can see so far to other solutions given and yours as well @Kangaroo976, the list is sorted in this way:

[4, 3, 7, 2, 10, 1, 8, 2, 4, 3]
[['LEFT'], ['LEFT'], ['LEFT'], ['LEFT'], ['MAX VAL'], ['RIGHT'], ['RIGHT'], ['RIGHT'], ['RIGHT'], ['RIGHT']]

Instead I picture in a different way, so basically have 2 pipes which are 2 list with Max and min value alternatively, so the same input list with my implementation, I would sort the list in 2 like this:

# MAX       # MIN
|| 10   *   1 ||
|| 8   *    2 ||
|| 7   *    2 ||
|| 4   *    3 ||
|| 4   *    3 ||

Then you calculate each 2 index 2 times for each numbers, for so you have groups or clusters as follow:

# 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)

In case the list has odds numbers like [4, 1, 8, 2, 7, 3, 2, 4, 10] the calculation is slightly different:

# 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

First Solution

Note, is sightly slower than your original

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

Second Solution

Hence Following this logic, and sorting the list before and devide the list in a Divide-and-conquer fashion I come up with this solution:

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

Benchmarking

original = min(timeit.Timer(original_).repeat(1, 20))
print(mine)
print(original)
print('==='*15)
print(min(mine, original))

Output

5.1045565999999996  # Mine
5.519946699999999   # Kangaroo976
=============================================
5.1045565999999996

Answer 2

Since you're alternating the larger and smaller numbers, you'll have a small number between two bigger numbers at each alternate spot. Something like bignum smallnum bignum smallnum..... You can easily arrange the bigger numbers, starting with the biggest numbers in the middle and consequently smaller ones wider out.
Now, all arrangements of smaller numbers would give the same result.

Let's say the current arrangement of numbers is a b c d e, where the numbers in increasing order are b < d < e < a < c.

1. Current difference: (a-b) + (c-b) + (c-d) + (e-d) = a+e+(2*c)-(2*b)-(2*d)
2. Let's swap b and d. Now the sequence becomes a d c b e. New difference = (a-d) + (c-d) + (c-b) + (e-b) = a+e+(2*c)-(2*b)-(2*d), which is same as the previous difference.
3. Try swapping a with e, that will also give the same result.

Arranging the bigger numbers is the important part, getting the bigger ones in the middle, because they contribute twice to the total difference. After that, the smaller numbers can be inserted in any order, since that doesn't effect the total difference.

Answer 3

😅 I realize I misread your question and see that you already conceived of the approach I described below (i.e. interleave the biggest and smallest values, trying both the minimum and the maximum as the innermost value). So in any case, all I will leave is my implementation and the code for testing against the brute force. The testing code shows that this "solution" is working essentially for all cases, and is significantly faster than the brute force approach (but there is still the matter of proof).

My code:

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)))

The brute force approach:

def brute_force(l):
    result = 0

    for i in itertools.permutations(l):
        if diff_sum(i) > result:
            result = diff_sum(i)

    return result

And for testing:

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}'

Answer 4

analyzing brute force results, I identified a few patterns of value order that I believe can be leveraged to compute the result quickly:

• The middle value is always first (or last in the mirror order)
• For odd sized lists, the middle value of the remaining elements is always last
• Remaining values (excluding first and odd's last) alternate between the upper half and lower half of the sorted elements staring with either the upper or lower half
• The upper and lower halves are either in ascending or descending order

Based on this observation (conjecture), the function would have at most 8 patterns to check:

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]

To validate this I compared results against a brute force function on randomly generated lists of various sizes:

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

Although I don't have a formal proof, this seems to work (and is very fast).

Answer 5

It seems like a good idea. You would want to maximize every single difference, so you would start with the highest than maximize that difference by putting both of the lowest elements, than the highest and so on. When I thought about the question that seemed like the best idea. Even though I don't think we need dequeue for 100 elements. I will try it out!