python - 确定两个列表的元素的分组程度

Question

我想做的是确定两个字符串的公共(public)元素的分组程度。可能已经有一个数学函数或 scipy/numpy/etc 函数可以执行此操作。我只是不知道它叫什么。我已经用谷歌搜索过了。例如:

该集合将获得满分(所有类似元素都分组):

['a','a','a','b','b','b']

也会:

['b','b','b','a','a','a']

这个系列会有一个较低的分数:

['a','a','b','b','b','a']

这个系列的得分非常低:

['a','b','a','b','a','b']

我可以想到几种方法来实现这一点，我只是想知道是否已经有一个定义此类事物的函数/算法。

我想到也许可以根据字符串中离散值的计数生成一个完美分组的字符串，并计算实际字符串和完美字符串之间的编辑距离。例如，比较:

['a','a','a','b','b','b']

至:

['b','b','b','a','a','a']

但同样，我正在寻找该算法是否已经有名称和实现。

Answer 1

我想不出任何现有的衡量标准，但似乎很容易制定一个衡量标准。您要求的是计算数组中的组数。

我的指标:数组长度除以组数

定义:

def metric(lst):
    L = len(lst)
    n = len(list(itertools.groupby(lst, lambda x: x)))
    return L/float(n)   # you can omit float if python 3

groupby 将计算数组 lst 中相同元素的 block 数。您不想像通常使用 groupby 那样对它进行排序，因为您正在计算 lst 元素中的更改。然后我们用lst的长度除以 block 的数量来找到“平均 block 长度”。这应该符合您的要求。

您可能需要衡量指标。在上面的情况下，它会支持更长的数组和更少的 block 。例如，您可以考虑 L 的平方根，以使指标遵循 yield 递减定律。