3

我需要一个序列中元素之间的比较索引。该索引是序列中相邻元素之间所有绝对比较的总和与序列及其长度可以具有的最大值之间的商。

例如，序列s1 = [0, 1, 2]和分别s2 = [0, 2, 1]具有绝对比较[1, 1]和[2, 1]。没有其他长度为 3 的序列组合具有比 3 更高的绝对比较和值。因此，对于 s1 和 s2，比较索引应该是 2/3 和 3/3。

这些序列总是有整数 from 0tolength - 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对于比较字符串（长度）中的每个项目，将有这些最大差异之一（的length-1）。因此最大值将是(length-1)**2。

但是，您似乎暗示长度 3 的最大值是3，那么为什么[0, 2, 0]无效（产生[2, 2]的总和为4）？

您提到必须包含从0to的所有整数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 回答