Сортировка списка по частоте появления элементов

#python #сортировка #task #dict

Я пытаюсь решать задачи на checkio, и у меня появилась проблема.

Задача:

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

[4, 6, 2, 2, 6, 4, 4, 4] == [4, 4, 4, 4, 6, 6, 2, 2]
['bob', 'bob', 'carl', 'alex', 'bob'] == ['bob', 'bob', 'bob', 'carl', 'alex']
[17, 99, 42] == [17, 99, 42] 


Если два элемента появляются одинаковое число раз, они должны записываться в том
же порядке, что и в первое появление в изначальном листе. 

Я использую код:

items1 = ["bob", "bob", "carl", "alex", "bob"]
items2 = [1, 2, 2, 1]
items3 = [4, 6, 2, 2, 6, 4, 4, 4]


def frequency_sort(items):
    result = []
    m = dict(pd.value_counts(items))
    print('Dictionary from list: ', m)
    for i in items:
        if items.count(i) == 1:
            return items
        elif items.count(i) == 0:
            return items
        else:
            for item in m:
                for i1 in range(0, m[item]):
                    result.append(item)
            return result
    return items


Результат:

Input data:  ['bob', 'bob', 'carl', 'alex', 'bob']
Dictionary from list:  {'bob': 3, 'alex': 1, 'carl': 1}
Result: ['bob', 'bob', 'bob', 'alex', 'carl']
**Must be: ['bob', 'bob', 'bob', 'carl', 'alex']**

Input data:  [1, 2, 2, 1]
Dictionary from list:  {2: 2, 1: 2}
Result: [2, 2, 1, 1]
**Must be: [1, 1, 2, 2]**

Input data:  [4, 6, 2, 2, 6, 4, 4, 4]
Dictionary from list:  {4: 4, 6: 2, 2: 2}
Result: [4, 4, 4, 4, 6, 6, 2, 2]


Код не работает. Есть 2 ошибки, они выделены.
Я не понимаю как словарь при преобразовании сортирует мой лист. Пытался отключить
сортировку: m = dict(pd.value_counts(items, sort=False)) Но получилось не очень :

Input data:  ['bob', 'bob', 'carl', 'alex', 'bob']
Dictionary from list:  {'carl': 1, 'bob': 3, 'alex': 1}
['carl', 'bob', 'bob', 'bob', 'alex']

Input data:  [1, 2, 2, 1]
Dictionary from list:  {1: 2, 2: 2}
[1, 1, 2, 2]

Input data:  [4, 6, 2, 2, 6, 4, 4, 4]
Dictionary from list:  {2: 2, 4: 4, 6: 2}
[2, 2, 4, 4, 4, 4, 6, 6]


Как решить задачу?
Пробовал сделать через листы, но запнулся.
    

Ответы

Ответ 1

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

result = []
for x in [x for i, x in enumerate(items) if i == items.index(x)]:
   result.extend([x]*items.count(x))


или даже вот так, что по сути тоже самое

def frequency_sort(items):
    result = []
    for i, x in enumerate(items):
       if i == items.index(x):
          result.extend([x]*items.count(x))
    return result


Update

def frequency_sort(items):
    temp = []
    for i, x in enumerate(items):
       if i == items.index(x):
          temp.append([x, [items.count(x), len(items)-i]])
    temp = sorted(temp, key = lambda x: x[1], reverse=True)
    result = []
    for x in temp:
       result.extend([x[0]]*x[1][0])
    return result


Ответ 2

Возможно, такой вариант вас устроит:

from collections import Counter
from itertools import chain

def freqlst(lst: list)-> list:
    return list(chain(*[ [k,]*v for k,v in Counter(lst).items()]))


Пррверяем:

print(freqlst([4, 6, 2, 2, 6, 4, 4, 4])) # [4, 4, 4, 4, 6, 6, 2, 2]
print(freqlst(['bob', 'bob', 'carl', 'alex', 'bob'])) # ['bob', 'bob', 'bob', 'carl',
'alex']
print(freqlst([17, 99, 42])) # [17, 99, 42]


Ответ 3

Я решил задачу следующим образом (UPD):

def frequency_sort(items: list) -> list:
    counts = {x:items.count(x) for x in items}
    sorted_counts = {k: counts[k] for k in sorted(counts.keys(), key=counts.get,
reverse=True)}
    result = [x for x in sorted_counts for _ in range(sorted_counts[x])]

    return result


Примечание: данный код работает, начиная с версии 3.7.

counts — это словарь, в котором ключами являются элементы списка items, а значениями
— количество вхождений соответствующего ключа в список items.

sorted_counts — это словарь counts, отсортированный по значениям ключей в обратном
порядке.

Словари, начиная с Python 3.7 сохраняют порядок, поэтому отлично подходят под наши
цели и удовлетворяют одному из условий задачи.

Всё что остаётся — это преобразовать полученный словарь в новый список (result).
Этим занимается списковое включение, которое можно переписать следующим образом:

result = []
for x in sorted_counts:
    for _ in range(sorted_counts[x]):
        result.append(x)



Тесты:

print(frequency_sort(items1))  # ['bob', 'bob', 'bob', 'carl', 'alex']
print(frequency_sort(items2))  # [1, 1, 2, 2]
print(frequency_sort(items3))  # [4, 4, 4, 4, 6, 6, 2, 2]

# UPD: Тест из комментария
print(frequency_sort(items4))  # [4, 4, 4, 4, 2, 2, 2, 6, 6]


Ответ 4

lst = [4, 6, 2, 2, 6, 4, 4, 4]
result = [r for s in sorted(set(lst), key=lst.index) for r in (a for a in lst if a == s)]


Ответ 5

def frequency_sort(items):

    temp = []
    sort_dict = {x: items.count(x) for x in items}
    for k, v in sorted(sort_dict.items(), key=lambda x: x[1], reverse=True):
        temp.extend([k] * v)
    return temp