Python按频率对字符串进行排序 - 无法使用sorted()函数进行排序

Question

我有一个问题，需要按频率对简单字符串进行排序（我输入一个字符串，需要输出一个按降序排列的已排序字符串）。

让我举个例子（原始单词包含4个e，2个s，1个t，1个r和1个d；因此这些会被排序）：

In [1]: frequency_sort("treeseeds")
Out [1]: "eeeesstrd"

大多数在Stack Overflow上的解决方案都指出我应该使用sorted()函数来获取结果，然而，它只能处理某些情况。

我编写了两个函数，本应该起作用，但是它们似乎都不能处理我的特定输入（见下文）。

第一个函数：

def frequency_sort(s):
    s_sorted = sorted(s, key=s.count, reverse=True)
    s_sorted = ''.join(c for c in s_sorted)
    return s_sorted

第二个函数：

import collections
def frequency_sort_with_counter(s):
    counter = collections.Counter(s)
    s_sorted = sorted(s, key=counter.get, reverse=True)
    s_sorted = ''.join(c for c in s_sorted)
    return s_sorted

使用这两个函数，我的输出结果如下：

第一个输出结果是正常的：

In [1]: frequency_sort("loveleee")
Out [1]: "eeeellov"

第二个输出并不是很多。

In [2]: frequency_sort("loveleel")
Out [2]: "leleelov"

第三个输出完全混乱：

In [3]: frequency_sort("oloveleelo")
Out [3]: "oloeleelov"

可能出了什么问题？这与'o'和'l'字符有关吗？还是我漏掉了什么？

- borthkror

---

我认为你忘记添加第三个函数了。 - Christian König

可能是在列表中按出现频率排序的重复问题。 - depperm

Answer 1

在一个字符串中，如果有多个字符出现的次数相同，你提出的算法无法区分出出现次数相同的字符。可以通过使用频率和字符本身的元组进行排序来解决这个问题；例如：

In [7]: def frequency_sort(s):
        s_sorted = sorted(s, key=lambda c: (s.count(c), c), reverse=True)
        s_sorted = ''.join(c for c in s_sorted)
        return s_sorted
   ...: 

In [8]: frequency_sort("loveleel")
Out[8]: 'llleeevo'

- jakevdp

Answer 2

在您的第三种情况中，有3个字母具有相同的计数，因此它们被放在一起，您可以首先按字母表顺序排序，然后按频率排序以排列字母如下：

s_sorted = ''.join(sorted(sorted(s), key=lambda x: s.count(x), reverse=True))

输出：

eeellloooav

或者你可以反转它：

s_sorted = ''.join(sorted(sorted(s, reverse=True), key=lambda x: s.count(x), reverse=True))

输出：

ooollleeeva

- Mohd

Answer 3

问题在于sort和sorted是稳定排序。因此，如果两个值“相等”（在这种情况下key(item1) == key(item2)），它们将按照它们在sort之前的顺序出现。

例如，在您的最后一个案例中，您有：

>>> from collections import Counter

>>> Counter("oloveleelo")
Counter({'e': 3, 'l': 3, 'o': 3, 'v': 1})

所以'e'，'l'和'o'具有相同的key，因此它们将像原来一样出现："oloeleelo"，然后只有一个具有不同计数的字符：'v'。

如果您不关心具有相等计数的元素的顺序（只是它们按字符分组），则甚至不需要sorted，只需展平Counter.most_common的结果即可：

>>> ''.join([item for item, cnt in Counter("oloveleelo").most_common() for _ in range(cnt)])
'llleeeooov'
>>> ''.join([item for item, cnt in Counter("loveleel").most_common() for _ in range(cnt)])
'eeelllov'
>>> ''.join([item for item, cnt in Counter("loveleee").most_common() for _ in range(cnt)])
'eeeellov'

- MSeifert