Сравнение смежных элементов в последовательностях

Question

Мне нужен индекс сравнения между элементами в последовательности. Этот индекс является фактором между суммой всех абсолютных сравнений между соседними элементами в последовательности и самым высоким значением, которое может иметь последовательность с его длиной.

Так, например, последовательности s1 = [0, 1, 2] и s2 = [0, 2, 1] имеют абсолютные сравнения [1, 1] и [2, 1], соответственно. Нет другой комбинации последовательностей с длиной 3 с более высокой суммой абсолютных сравнений, чем 3. Таким образом, индекс сравнения должен быть 2/3 и 3/3 для s1 и s2.

Эти последовательности всегда имеют целые числа от 0 до length - 1 и могут иметь несмежные повторяющиеся элементы, такие как [0, 1, 0, 1, 0]. Эти последовательности имеют все целые числа между их младшими и высшими значениями элементов.

Мне нужна функция для вычисления максимального значения абсолютных сравнений, которое может иметь последовательность с заданной длиной. Функция, которую я написал (наивысшая), возвращает неверные результаты. Я написал этот код:

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

Answer 1

Самый простой способ для создания списка является просто сделать:

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

Что касается вашего сравнения, максимальное значение всегда будет максимально сопровождаемый минимальный, повторный. Например: для длины 4:

[3, 0, 3, 0] 

Поскольку это будет производить максимальную разницу каждый раз. Будет одна из этих максимальных разностей (length-1) для каждого элемента в строке сравнения (длиной length-1). Следовательно, максимум будет (length-1)**2.

Однако, как представляется, означает, что максимум для длины 3 был 3, так почему [0, 2, 0] не действует (производство [2, 2], который суммирует в 4)?

Вы упомянули, что все целые числа от 0 до length-1 должны быть включены, но это делает некоторые из ваших примеров (например: [0, 1, 0]) недействительными. Это также противоречит идее, что любые элементы могут быть повторены (если список длины n должен содержать от 0 до n-1, он не может иметь повторений).

Если этот случай верен, тогда ваш вопрос будет несколько похож на проблему создания матрицы сглаживания.

В случае заказа диапазона от 0 до len-1, чтобы получить максимальную разницу, оптимальный алгоритм должен работать от 0 и ниже от len-1, добавляя низкие значения к самой высокой стороне 'из списка, и наоборот:

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

который дает нам:

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 

Показано, что этот алгоритм соответствует грубой силы подход для получения наилучшего возможного результата.

Далее следует более общее решение:

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

Что дает:

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 

который соответствует предыдущим результатам, где это возможно.