按元素出现频率对元组列表进行排序

Question

我刚接触Python，尝试了很多不同的东西，遇到了一个问题，我觉得自己“解决”了，但代码看起来不太对劲——我强烈怀疑还有更好的方法来达到想要的结果。

顺便说一下，我在Windows上使用的是最新版本的Python 3。

问题定义

简单来说，我要做的是对一组成对的数据进行排序，目的是把那些包含出现次数最少的元素的对排到前面。

这些对的形式是 [i,j]，其中 0 <= i <= j < n，这里的 n 是已知的元素最大值。列表中没有重复的对。

元素 i 的计数是指在形式为 [i,j]、[j,i] 和 [i,i] 的对中，i 出现的次数（j 是任何能形成有效对的值）。

在排序后的结果中，如果一对 [i,j] 的计数小于另一对 [k,l] 的计数，或者两者计数相等但 j 的计数小于 l 的计数，那么 [i,j] 应该排在 [k,l] 前面（如果 j 和 l 的计数相等，它们的顺序可以互换——我不太在意排序是否稳定，如果能稳定就更好了）。

在排序后的结果中，如果一对 [i,j] 的最小计数小于另一对 [k,l] 的最小计数，或者两者的最小计数相等但最大计数小于另一对的最大计数，那么 [i,j] 应该排在 [k,l] 前面。
换句话说，如果这对是 [0,1]，而 1 的计数是1，但 0 的计数是400，那么这对仍然应该排在列表的前面（或者至少很靠前）——它们需要根据对中出现次数最少的元素进行排序。

这是我构造的一个例子：

input   [[0,0],[1,2],[1,4],[2,2],[2,3],[3,3],[3,4]]

这是每个元素的计数和它们来源的对：

0: 1   [0,0]
1: 2   [1,2],[1,4]
2: 3   [1,2],[2,2],[2,3]
3: 3   [2,3],[3,3],[3,4]
4: 2   [1,4],[3,4]

这是结果，以及每对的得分：

output: [[0,0],[1,4],[1,2],[3,4],[2,2],[2,3],[3,3]]
scores:   1     1-2   1-3   2-3   3     3     3

在这里，0 的计数是1（它出现在 一个 对中，虽然出现了两次），所以排在第一。1 的计数是2，所以排在第二——[1,4] 排在 [1,2] 前面，因为 4 的计数是2，而 2 的计数是3，依此类推。

我目前的解决方案

如前所述，我认为这个实现是准确的，但我觉得一定还有更好的方法来做这件事。无论如何，这是我目前的代码：

#my implementation uncommented to reduce post size, see history for comments
def sortPairList( data , n ):
    count = []
    for i in range(0,n):
        count.append( 0 )

    #count up the data
    for p in data:
        count[p[0]] += 1
        if p[1] != p[0]:
            count[p[1]] += 1

    maxcount = 0
    for i in range(0,n):
        if count[i] > maxcount:
            maxcount = count[i]

    def elementFrequency(p):
        if count[ p[0] ] < count[ p[1] ]:
            return count[ p[0] ] + float(count[ p[1] ]) / (maxcount+1)
        else:
            return count[ p[1] ] + float(count[ p[0] ]) / (maxcount+1)

    data.sort( key=elementFrequency )

有没有更“Pythonic”的做法？
或者我目前的尝试有什么问题吗？

新的测试案例（见答案的评论）

input:    [[0,0],[0,3],[0,5],[0,7],[1,1],[1,2],[1,8],[2,4],[2,5],[3,4],[3,5],[3,9],[4,4],[4,7],[4,8],[6,8],[7,7],[7,9],[8,9]]
expected: [[6,8],[1,1],[1,2],[2,5],[0,5],[1,8],[3,5],[3,9],[7,9],[8,9],[2,4],[0,0],[0,3],[0,7],[7,7],[3,4],[4,7],[4,8],[4,4]]

Answer 1

这个方法和KennyTM的解决方案类似，不过适用于Python 2.5或更高版本：

import collections

def sort_by_occurence(sequences):
    tally = collections.defaultdict(int)
    for sequence in sequences:
        for item in sequence:
            tally[item] += 1
    sequences.sort(key=lambda x:map(tally.get, x))


pair_list = [[0,0],[1,2],[1,4],[2,2],[2,3],[3,3],[3,4]]
sort_by_occurence(pair_list)
print pair_list

Answer 2

>>> n = 4
>>> freqs = {i: sum(i in j for j in inp) for i in range(n+1)}
>>> def key(x):
    a, b = x
    return min(freqs[a], freqs[b]), max(freqs[a], freqs[b])

>>> sorted(inp, key=key)

附言：请注意，input这个变量名不好，因为它会和内置的功能冲突。

Answer 3

我可能会用一个叫做 Counter 的东西来统计数据。（需要Python版本≥2.7或≥3.1）

from collections import Counter
from itertools import chain
def sortPairList2(data):
    tally = Counter(chain(*map(set, data)))
    data.sort(key=lambda x: sorted(tally[i] for i in x))

注意以下几点：

1. 你可以用 lambda 来创建一个匿名函数。比如说，

   >>> c = 4
   >>> a = lambda p: p - c
   >>> a(7)
   3
   

2. 排序的关键值不一定是数字。任何可以比较的东西都可以用作关键函数的返回值。在我的代码中，我用了一个 list 来进行排序。

3. 在Python中，有很多更简单的方法可以实现你原来的代码。

   • 可以用 count = [0] * n 来初始化 count，而不是用那个循环。
   • 可以用 max函数 来获取 maxcount。也就是说，maxcount = max(count)

4. 列表推导式 在Python中使用得非常多。如果你的目标是把一个可迭代的东西转换成另一个可迭代的东西，建议用推导式而不是循环。