根据成对元素的频率对列表进行排序

Question

我完全不懂Python，但在尝试各种随机代码时，发现了一个问题，我相信我已经“解决”了这个问题，但是代码感觉不太对-我强烈怀疑有更好的方法来获得所需的结果。

FYI-我在Windows上使用最新版本的Python 3。

问题定义

简而言之，我正在对一对列表进行排序，以使包含出现次数最少的对应元素的对位于前面。

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

元素i的计数是形式为[i,j]、[j,i]和[i,i]的配对（而不是成对元素）的数量，其中j是任何导致有效对的值。

在排序结果中，如果count(i) < count(k)或count(i) == count(k)并且count(j) < count(l)，则对[i,j]应该出现在对[k,l]之前（如果count(j) == count(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))，则对[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]]

以下是各个元素的计数及其来源对：

这里是需要翻译的内容，涉及IT技术。

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]，因为4出现了两次，而2出现了三次，以此类推。

我目前的解决方案

正如所说，我相信这个实现方法是准确的，但感觉肯定有更好的方法来做到这一点。无论如何，这就是我目前的做法：

#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]]

- DMA57361

---

在你的例子中，第二个位置上的4和2都有两个计数。由于3也有两个计数，所以你的输出与输入没有任何关联。换句话说，根据你的要求，input已经是排序好的。 - SilentGhost

@SilentGhost 在这个例子中，数字 2 出现了三次（而不是两次），因为它出现在 [1,2]、[2,2] 和 [2,3] 中。数字 3 也出现了三次，分别是在 [2,3]、[3,3] 和 [3,4] 中。 - DMA57361

但是如果 0 的数量也是两个，那么为什么它应该排在 1 之前呢？ - SilentGhost

@SilentGhost - 因为 0 只出现在一个配对中（它出现两次的事实对我来说是无关紧要的）。请注意，我还详细阐述了如何从 input 得出 output 的更多细节。 - DMA57361

Answer 1

我可能会使用一个计数器（需要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. You can create an anonymous function with lambda. For example,

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

2. The sort key need not be a number. Anything comparable can be used as the return value of the key function. In my code, a list is used for ordering.

3. There are many simpler idioms in Python for your original code.

   • The count can be initialized using count = [0] * n instead of that loop.
   • The maxcount can be obtained with the max function. maxcount = max(count)

4. List comprehension is used a lot in Python. If your target is to transform an iterable into another iterable, prefer comprehension over loops.

- kennytm

---

看起来很有前途，简洁得多。不幸的是，我当前的位置没有Python解释器可用 - 但一旦回家我会尝试一下这个。 - DMA57361

@DMA：有许多语言的在线编译器。关于这段代码，请参见http://www.ideone.com/5VFuw。 - kennytm

@KennyTM - 我在 codepad 上尝试了一下，但由于导入失败（可能是版本不匹配），所以没有成功。你提到的其他点也非常有用，谢谢。今晚我会使用一些真实输入进行测试，看看结果如何。 - DMA57361

@KennyTM - 在第二个测试用例中，我没有得到你建议的预期结果，事实证明我把问题定义弄糟了。对此感到抱歉，如果你感兴趣，问题已经更新。我还不太理解你的建议，我需要先阅读一些资料，然后才能尝试修复它。 - DMA57361

@KennyTM - 感谢您的帮助，这很好地完成了工作，您在答案中提供的额外要点看起来非常有用。 - DMA57361

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 是一个不好的变量名，因为它会掩盖内置函数。

- SilentGhost

---

“input” 仅是我的问题举例中的变量名，并非真实的变量名，但我会在以后注意这一点。这些看起来很有前途，今晚我会用一些真实的输入进行测试。 - DMA57361

我在第二个测试案例中没有得到你的建议所预期的结果，原来是我弄错了问题的定义。如果你感兴趣，对不起，问题已经更新了。我通过使用if( aa < bb ): return aa * n + bb else: return bb * n + aa替换了你的第一个建议（我认为使用求和方法预计算频率可能适合我）。我还没有理解你的第二个建议，所以我要再看一下。 - DMA57361

谢谢您的帮助，它很有效，但今天我会把选项给KennyTM，因为他在帖子中提供了额外的信息。 - DMA57361

@DMA：希望你会采纳他的建议而不是我的，谢谢。 - SilentGhost

Answer 3

虽然KennyTM的解决方案可行，但我尝试自己做。

我的解决方案是预先计算频率并将其存储在字典中，其中str(n)是键。我在将Python2中已知的比较函数更改为Python3中使用的键时遇到了一些麻烦，但我在ActiveState code找到了解决方法。

item_cnt = {}

def icount(n):
    return item_cnt[str(n)]

def add_item(n):
    sn = str(n)
    try:
        item_cnt[sn] += 1
    except KeyError:
        item_cnt[sn] = 1

# sort callback
def cmp_items(ij, kl):
    i, j = ij
    k, l = kl
    if icount(i) < icount(k) or icount(i) == icount(k) and icount(j) < icount(l):
        return -1
    return 1

input = [[0,0],[1,2],[1,4],[2,2],[2,3],[3,3],[3,4]]
# count all items
for (i, j) in input:
    add_item(i)
    add_item(j)

# works with Python 2.x
#input.sort(cmp_items)
# works with Python2.6 and Python 3.x
# to convert compare function to key look at:
# http://code.activestate.com/recipes/576653-convert-a-cmp-function-to-a-key-function/
input.sort(key=cmp_to_key(cmp_items))
print(input)

- Michał Niklas

Answer 4

类似于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

- pillmuncher