python - Python:リストで最も頻繁に使用されるアイテムを取得する

Question

タプルのリストが与えられた場合、最も頻繁に発生するタプルを取得しようとしていますが、「共同勝者」が存在する場合は、ランダムに選択する必要があります。

tups = [ (1,2), (3,4), (5,6), (1,2), (3,4) ]

上記のリストは、上記のリストに対してランダムにまたはいずれ(1,2)かを返す必要があります(3,4)

Answer 1

最初に Counter を使用して、最も繰り返されるタプルを見つけることができます。次に、必要なタプルを見つけ、最後にランダム化して最初の値を取得します。

from collections import Counter
import random

tups = [ (1,2), (3,4), (5,6), (1,2), (3,4) ]
lst = Counter(tups).most_common()
highest_count = max([i[1] for i in lst])
values = [i[0] for i in lst if i[1] == highest_count]
random.shuffle(values)
print values[0]

Answer 2

これは時間内にあなたの仕事をするはずですo(n):

>>> from random import shuffle
>>> from collections import Counter
>>>
>>> tups = [(1,2), (3,4), (5,6), (1,2), (3,4)]
>>> c = Counter(tups)                            # count frequencies
>>> m = max(v for _, v in c.iteritems())         # get max frq
>>> r = [k for k, v in c.iteritems() if v == m]  # all items with highest frq
>>> shuffle(r)                                   # if you really need random - shuffle
>>> print r[0]
(3, 4)

Answer 3

最初にリストをソートして、頻度でソートされたタプルを取得できます。その後、線形スキャンにより、リストから最も頻繁に使用されるタプルを取得できます。総時間O(nlogn)

>>> tups = [ (1,2), (3,4), (5,6), (1,2), (3,4) ]
>>> 
>>> sorted(tups)
[(1, 2), (1, 2), (3, 4), (3, 4), (5, 6)]