Выбирайте словарные ключи только в том случае, если их значения не имеют определенного количества дубликатов

Question

Учитывая словарь и ограничение на количество ключей в новом словаре, я хотел бы, чтобы новый словарь содержал ключи с наивысшими значениями.

Данный код является:

dict = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1 }

Я хочу получить новый словарь, в котором есть ключи с максимальными значениями ограничения длины.

Например, для limit = 1 новый dict будет

{'apple':5} 

, еслиlimit = 2

{'apple':5, 'pears':4}

Я пробовал это:

return dict(sorted(dictation.items(),key=lambda x: -x[1])[:limit])

, но когда я пытаюсь ограничить = 3, я получаю

{'apple':5, 'pears':4, 'orange':3}

Но это не должно включатьorange: 3 , потому что orange и kiwi имеют одинаковый приоритет , если мы добавим киви и orange, он превысит лимит, поэтому он не должен включать оба.Я должен вернуть

{'apple':5, 'pears':4}

Answer 1

Это вычислительно не очень хорошо, но работает.Он создает объект Counter , чтобы получить отсортированный вывод для ваших данных, и инвертированный defaultdict , который содержит список, соответствующий счету, - он создает результат, используя как и некоторую математику:

from collections import defaultdict, Counter

def gimme(d,n):
    c = Counter(d)
    grpd = defaultdict(list)
    for key,value in c.items():
        grpd[value].append(key)


    result = {}
    for key,value in c.most_common():
        if len(grpd[value])+len(result) <= n:
            result.update( {k:value for k in grpd[value] } )
        else:
            break
    return result

Тест:

data = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1 }

for k in range(10):
    print(k, gimme(data,k))

Выход:

0 {}
1 {'apple': 5}
2 {'apple': 5, 'pears': 4}
3 {'apple': 5, 'pears': 4}
4 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3}
5 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3}
6 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3, 'banana': 1}
7 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3, 'banana': 1}
8 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3, 'banana': 1}
9 {'apple': 5, 'pears': 4, 'orange': 3, 'kiwi': 3, 'banana': 1}

Answer 2

Как вы заметили, фильтрация по верху n не исключает по умолчанию все равные значения, которые превышают указанный предел.Это специально.

Хитрость заключается в том, чтобы рассмотреть (n + 1) наивысшее значение и убедиться, что значения в вашем словаре все выше, чем это число:

from heapq import nlargest

dictation = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1}

n = 3
largest_items = nlargest(n+1, dictation.items(), key=lambda x: x[1])
n_plus_one_value = largest_items[-1][1]

res = {k: v for k, v in largest_items if v > n_plus_one_value}

print(res)

{'apple': 5, 'pears': 4}

Мы предполагаем здесь len(largest_items) < n, иначе вы можете просто взять входной словарь в качестве результата.

---

Понимание словаря кажется дорогим.Для больших входов вы можете использовать bisect, что-то вроде:

from heapq import nlargest
from operator import itemgetter
from bisect import bisect

dictation = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1}

n = 3
largest_items = nlargest(n+1, dictation.items(), key=lambda x: x[1])
n_plus_one_value = largest_items[-1][1]

index = bisect(list(map(itemgetter(1), largest_items))[::-1], n_plus_one_value)

res = dict(largest_items[:len(largest_items) - index])

print(res)

{'apple': 5, 'pears': 4}

Answer 3

Можно было бы использовать collections.Counter и most_common(n).Затем вы можете взять еще один, если потребуется, и продолжать нажимать, пока не изменится последнее значение:

from collections import Counter

dct = {'apple':5, 'pears':4, 'orange':3, 'kiwi':3, 'banana':1}
n = 3

items = Counter(dictation).most_common(n+1)
last_val = items[-1][1]
if len(items) > n:
    while items[-1][1] == last_val:
        items.pop()

new = dict(items)
# {'apple': 5, 'pears': 4}