查找一个范围，该范围生成最接近“正确”集的集。

Question

我正在设计一种算法，它可以找到最适合超级集合中定义的正确数字集的一系列数字。我在下面附上了一张图片，希望能准确地阐明我的意思。

​

​

解决上述问题的一个理想解决方案是范围为2-5，这将产生以下结果：

​

​

对于该算法，我没有明确的性能度量标准，但我认为这将是一个良好的开端：

​

^^以上应该是'+‘而不是减号。

蛮力强迫并不理想，因为这些集合可能包含数千个数字。我目前的想法是对正确的集合进行平均，并加/减一个标准差，但必须有更好的方法。

Answer 1

无论您最终决定了什么度量，如果在长度为n的范围内计算度量需要O(n)时间，那么这可以在O(n^3)时间内求解为最优:您所需要做的就是对数字(O(n log n))排序，然后对每个O(n^2)可能的组合(起始数、结束数)从这个范围内计算出您的度量，每组合使用O(n)时间。

事实上，大多数度量都可以在恒定时间内递增计算，这样就可以得到O(n^2)，而不会有太多麻烦。例如，您指定的度量(我同意，BTW可能不是最好的，因为0很容易出现在分母中)可以很容易地递增计算:对于一个范围(a，b)，记录正确猜测的计数和错误猜测的计数；根据这两个数字计算您的度量只是一个减法和一个除法。然后，要计算范围(a，b+1)的答案，只需增加这两个总计中的一个是合适的。

我推荐什么标准？Jaccard指数总是在0到1之间，特别是总是定义的，前提是您正在比较的两个集合中至少有一个(在这里，范围中的数字和“定义正确集”中的数字)有多个元素。

[编辑：，只要您的度量具有完全合理的属性，使范围比所需的范围更宽永远不会使其更好，您可以比尝试输入中的所有对数字做得更好:您只需要在正确的集合中尝试所有对数字。如果正确的集合比总输入小得多，这将是一个巨大的胜利。]

Answer 2

我怀疑余弦相似可能是比较这两个多集(计数器)的一个更好的指标(如果计算成本更高)。不过，您需要调整Ai和Bi的值。

如果A是正确的多集，B是范围多集，那么需要考虑的是一些情况，所以在您的示例中大多数不确定这些情况有多相关。

1. Bi == Ai，Ai != 0:确切的情况。范围中的值与正确的大小写中的值完全相同。在您的示例中，i=4和i=5会发生这种情况。
2. Bi略高于Ai:这与multiset中的其他值一起发生。在这种情况下，应该有轻微的处罚。
3. Bi比Ai更多:例如Bi可能是100，Ai可能是30。在这种情况下，应该有一个中等到大型的罚款。
4. Bi比Ai多得多:例如Bi可能是1000，Ai可能是5。在这种情况下，应该有一个中等到大型的惩罚。
5. Bi == Ai，Ai == 0:这个病例很难确定。我在这个范围内，但在A或B中不存在，很可能会有一些恒定的点球。

最后，对于一些k >= 1和c >= 1，最好使用B‘和A’，而不是B和A。根据下面的Pythonic伪码计算。

Version 1:
    A' = 0
    if A[i] == B[i]:
        if A[i] == 0:
            B'[i] = 0
        else:
            B'[i] = c
    else:
        B'[i] = (A[i] - B[i])^k

好像k=1或k=2就行了。而c可以根据范围的大小来计算。

如果Bi不等于Ai这一事实使差别变得不敬，则公式简化为简单：

Version 2
    A' = 0
    if A[i] == B[i]:
        if A[i] == 0:
            B' = 0
        else:
            B'[i] = c
    else:
        B'[i] = b

其中b和c只是一些常量，c>b。我认为在c= 1和b=1或c=0和b=1的情况下，版本2简化为Jaccard索引。Jaccard索引的问题是，如果将A5 == B5 == 1和A10000 == B10000 == 1作为唯一的两个元素。对于范围为5,10000的Jaccard索引是1，这可能不是一个问题，但这是值得考虑的。