シーケンス内の隣接要素の比較

Question

シーケンスの要素間の比較のインデックスが必要です。このインデックスは、シーケンス内の隣接する要素間のすべての絶対比較の合計と、その長さを持つシーケンスが持つことができる最大値との間の商です。

例えば、配列s1 = [0, 1, 2]およびs2 = [0, 2, 1]はそれぞれ絶対比較が[1, 1]および[2, 1]である。 3以上の絶対値比較の合計値が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になります。

しかし、あなたは、なぜ有効な（4に合計[2, 2]を生産）ではない[0, 2, 0]で、長さ3の最大値が3だったことを示唆するものと思われましたか？

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 

を次の何

は、より一般的なソリューションです。