python - 按对元素的频率对列表对进行排序

Question

我是 Python 的新手，在尝试各种随机点点滴滴时，我发现了一个我相信我已经“解决”的问题，但是代码感觉不对- 我强烈怀疑会有更好的方法来获得预期的结果。

仅供引用 - 我在 Windows 上使用的是最新版本的 Python 3。

问题定义

简而言之，我正在做的是对一个对列表进行排序，这样包含出现在最少对中的元素的对被排序到前面。

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

元素的计数 i是形式中的对数(不是对元素)的简单计数 [i,j] , [j,i]和 [i,i]其中 j是产生有效对的任何值。

在排序结果中，一对[i,j]应该出现在一对 [k,l] 之前如果count(i) < count(k)或 count(i) == count(k)和 count(j) < count(l) (如果 count(j) == count(l) 这两个可以按任何顺序排列 - 我不担心排序是否稳定，不过会是一个奖励)。

在排序后的结果中，一对[i,j]应该出现在一对 [k,l] 之前如果
min(count(i),count(j)) < min(count(k),count(l))或者
min(count(i),count(j)) == min(count(k),count(l))和 max(count(i),count(j)) < max(count(k),count(l)) .
换句话说，如果这对是 [0,1]和 1计数为 1，但是 0计数为四百，该对仍应位于(或至少非常接近)列表的前面 - 他们需要按对中出现频率最低的元素进行排序。

这是我构建的人为示例:

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,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 )

关于更“Python”的方法有什么建议吗？
或者我当前的尝试有什么问题吗？

新测试用例(查看答案的评论)

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

我可能会使用 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. 您可以创建 an anonymous function with lambda .例如，

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

2. 排序键不必是数字。任何可比较的东西都可以用作键函数的返回值。在我的代码中，列表 用于排序。

3. 对于您的原始代码，Python 中有许多更简单的习语。

   • 可以使用 count = [0] * n 而不是该循环来初始化 count。
   • 可以用the max function 获得maxcount . maxcount = max(计数)

4. List comprehension在 Python 中被大量使用。如果您的目标是将一个可迭代对象转换为另一个可迭代对象，则更喜欢理解而不是循环。