CODEWITHSUNDEEP
pythonlistsequence
msampaio
msampaio

Reputation: 3433

Comparison between adjacent elements in sequences

I need an index of comparison between elements in a sequence. This index is the quotient between sum of all absolute comparisons between adjacent elements in a sequence, and the highest value that a sequence with its length can have.

For instance, the sequences s1 = [0, 1, 2] and s2 = [0, 2, 1] have absolute comparisons [1, 1], and [2, 1], respectively. There is no other combination of sequences with length 3 with a higher value of absolute comparisons sum than 3. Thus, comparison index should be 2/3 and 3/3 for s1 and s2.

These sequences always have integers from 0 to length - 1 and can have non-adjacent repeated elements, such as [0, 1, 0, 1, 0]. These sequences have all integers between their lower and highest elements values.

I need a function to calculate the highest value of absolute comparisons sum a sequence with a given length can have. The function I wrote (highest) returns wrong results. I wrote this code:

    def aux_pairs(seq):
        n = 2
        return [seq[i:i + n] for i in range(len(seq) - (n - 1))]

    def comparisons_sum(seq):
        return sum([abs(el[-1] - el[0]) for el in aux_pairs(seq)])

    def highest(seq):
        card = len(seq)
        pair = [0, card - 1]
        r = (pair * (card / 2))
        if card & 1 == 1:
            r.append(0)
        return comparisons_sum(r)

    def comparison_index(seq):
        return comparisons_sum(seq) / float(highest(seq))

Upvotes: 3

Views: 1523

Answers (1)

Gareth Latty
Gareth Latty

Reputation: 88977

The easiest way to produce your list is to simply do:

def comparisons(seq):
    return [abs(a-b) for a, b in zip(seq, seq[1:])]

As to your comparison, the highest value is always going to be the maximum followed by the minimum, repeated. E.g: for length 4:

[3, 0, 3, 0]

As this will produce the maximum difference each time. There will be one of these maximum differences (of length-1) for each item in the comparison string (of length length-1). Hence the maximum will be (length-1)**2.

However, you seemed to imply that the maximum for length 3 was 3, so why is [0, 2, 0] not valid (producing [2, 2] which sums to 4)?

You mentioned that all of the integers from 0 to length-1 must be included, but then this makes some of your examples (e.g: [0, 1, 0]) invalid. This also conflicts with the idea any elements can be repeated (if a list of length n must contain from 0 to n-1, it cannot have repeats).

If this case is true, then your question becomes somewhat similar to the problem of creating a dithering matrix.

In the case of ordering the range from 0 to len-1, to produce the maximum difference, the optimal algorithm is to work up from 0, and down from len-1, adding the low values to the highest 'side' of the list, and visa versa:

from collections import deque
from itertools import permutations
from operator import itemgetter

def comparisons(seq):
    return [abs(a-b) for a, b in zip(seq, seq[1:])]

def best_order(n):
    temp = deque([0, n-1])
    low = 1
    high = n-2
    while low < high:
        left = temp[0]
        right = temp[-1]
        if left < right:
            temp.append(low)
            temp.appendleft(high)
        else:
            temp.append(high)
            temp.appendleft(low)
        low += 1
        high -= 1
    if len(temp) < n:
        temp.append(low)
    return list(temp)

def brute_force(n):
    getcomp = itemgetter(2)
    return max([(list(a), comparisons(a), sum(comparisons(a))) for a in permutations(range(n))], key=getcomp)

for i in range(2, 6):
    print("Algorithmic:", best_order(i), comparisons(best_order(i)), sum(comparisons(best_order(i))))
    print("Brute Force:", *brute_force(i))

Which gives us:

Algorithmic: [0, 1] [1] 1
Brute Force: [0, 1] [1] 1
Algorithmic: [0, 2, 1] [2, 1] 3
Brute Force: [0, 2, 1] [2, 1] 3
Algorithmic: [2, 0, 3, 1] [2, 3, 2] 7
Brute Force: [1, 3, 0, 2] [2, 3, 2] 7
Algorithmic: [3, 0, 4, 1, 2] [3, 4, 3, 1] 11
Brute Force: [1, 3, 0, 4, 2] [2, 3, 4, 2] 11

Showing that this algorithm matches the brute force approach for producing the best result possible.

What follows is a more general solution:

from collections import deque

def comparisons(seq):
    return [abs(a-b) for a, b in zip(seq, seq[1:])]

def best_order(seq):
    pool = deque(sorted(seq))
    temp = deque([pool.popleft(), pool.pop()])
    try:
        while pool:
            if temp[0] < temp[-1]:
                temp.append(pool.popleft())
                temp.appendleft(pool.pop())
            else:
                temp.append(pool.pop())
                temp.appendleft(pool.popleft())
    except IndexError:
        pass
    return list(temp)

i = [0, 1, 2, 3, 4, 5, 6, 0, 0, 1, 1, 2, 2]
print("Algorithmic:", best_order(i), comparisons(best_order(i)), sum(comparisons(best_order(i))))
for n in range(2, 6):
    i = list(range(n))
    print("Algorithmic:", best_order(i), comparisons(best_order(i)), sum(comparisons(best_order(i))))

Which gives:

Algorithmic: [2, 1, 3, 0, 5, 0, 6, 0, 4, 1, 2, 1, 2] [1, 2, 3, 5, 5, 6, 6, 4, 3, 1, 1, 1] 38
Algorithmic: [0, 1] [1] 1
Algorithmic: [0, 2, 1] [2, 1] 3
Algorithmic: [2, 0, 3, 1] [2, 3, 2] 7
Algorithmic: [3, 0, 4, 1, 2] [3, 4, 3, 1] 11

Which matches the previous results where it can.

Upvotes: 5

Related Questions