序列跟随百分比

Question

问题陈述：一个人必须按顺序前往一组位置： Seq: L1 L2 L3 L4 L5 L6 (假设L1, L2是位置)

但他跟随的顺序不同：实际序列：L3 L1 L2 L4 L5 L6

现在我需要找出后面的 % 序列是什么。请记住，算法应该考虑 L4、L5、L6 仍然在 L3 之后。所以这不是一道简单的%题。

非常感谢任何帮助

Answer 1

我会尝试使用您的示例测试位置数组中每个连续位置之间的距离，如下所示：

distance from L1 to L2 = 1
distance from L2 to L3 = 2
distance from L3 to L4 = 3
distance from L4 to L5 = 1
distance from L5 to L6 = 1

then add them up...TTL = 8

A perfect, 100% score is 5
Our score is 8

The difference between our score and a perfect score is 8-5 = 3
The percentage is subtracted from 100% like so: 1.00 - 3/5 = 0.40 = 40%

Answer 2

这是一个称为 Longest Increasing Subsequence 的问题，有 O(n log n) 个算法。

要计算百分比，您只需找到 LIS(V)/length(V)。

这是 Python

中的示例实现 (O(n^2))

编辑：更改代码以明确指出 O(n) 步骤可以变成 O(log n)

def LIS(V):
    n = len(V)
    T = [0]*(n+1)

    L = 0
    for i in xrange(n):
        #this step can be a binary search
        j = max(j for j in xrange(L+1) if j==0 or V[T[j]] < V[i])

        T[j+1] = i
        L = max(L, j+1)

    return L/float(n)*100

print '{:.2f}%'.format(LIS([3, 1, 2, 4, 5, 6])) #83.33%
print '{:.2f}%'.format(LIS([1, 2, 3, 4, 5, 6])) #100.00%
print '{:.2f}%'.format(LIS([6, 1, 2, 5, 4, 3])) #50.00%

Answer 3

您应该考虑两个输入（初始序列和实际序列）的 Longest common Subsequence

将最长的公共子序列除以位置数，得到后面的 % 序列。

你的情况是 5/6 = .8333 = 83.33%

序列跟随百分比

Sequence following percentage

algorithm

statistics