3

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

たとえば、シーケンス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))
4

1 に答える 1

5

リストを作成する最も簡単な方法は、次のことを行うことです。

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

あなたの比較に関しては、最高値は常に最大値になり、次に最小値が繰り返されます。例：長さ4の場合：

[3, 0, 3, 0]

これにより、毎回最大の差が生じます。length-1（長さの）比較文字列の各項目には、これらの（の）最大の差の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

これは、可能な場合は以前の結果と一致します。

于 2012-04-23T11:32:10.000 に答える