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

Question

我在按频率对简单字符串进行排序时遇到问题（我得到一个字符串作为输入，我需要按降序返回一个排序后的字符串作为输出）。举个例子（原单词包含4个e，2个s，1个t，1个r，1个d，所以排序）：

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

Stack Overflow 上的大多数解决方案都指出我应该使用 sorted() 函数来获取结果，但是，它似乎只适用于某些情况。

我创建了两个应该可以工作的函数，但其中 none 似乎对我的特定输入起作用（见下文）。

第一个函数：

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' 字符？或者我只是错过了什么？

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'

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

Answer 3

问题是 sort 和 sorted 是稳定排序。因此，如果两个值是 "equal"（在本例中为 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'

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

Python Sort string by frequency - cannot sort with sorted() function

python

sorting

string

frequency