序列中相鄰元素之間的比較

Question

我需要序列中元素之間的比較索引。該索引是序列中相鄰元素之間的所有絕對比較的總和與具有其長度的序列可以具有的最高值之​​間的商。

例如，序列s1 = [0, 1, 2]和s2 = [0, 2, 1]具有絕對的比較[1, 1]，和[2, 1]，分別。沒有其他長度爲3的序列組合，絕對比較和的總和高於3.因此，對於s1和s2，比較指數應該是2/3和3/3。

這些序列總是具有從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 

這之前的結果在那裏可以匹配。