Поиск наиболее часто встречающегося вложенного списка с одинаковыми элементами

#python #list

Есть список с вложенными списками. Нужно найти наиболее часто встречающийся список.

Пример:

Input:

[[1,2,3],[2,5,6],[8,2,1],[2,3,1]]

Output:

[1,2,3] -> 2 шт

Списки [1,2,3] и [2,3,1] cчитаются равными.
    

Ответы

Ответ 1

Одной строкой (не считая импорта, инициализации s и вывода):

from collections import Counter
s = [[1,2,3],[2,5,6],[8,2,1],[2,3,1]]
sublist, count = max(Counter(tuple(sorted(x)) for x in s).items(), key=lambda x: x[1])
print('%s -> %d' % (list(sublist), count))


Разбор:


Превращаем s в набор сортированных кортежей (неизменяемых списков, по сути). Сортируем
потому, что по условию списки различающиеся только порядком одинаковы, а после сортировки
они становятся полностью совпадающими. Преобразование в кортеж нужно потому, что Counter
из следующего пункта может считать только хешируемые объекты (списки к таким объектам
не относятся, а вот кортежи - да): (tuple(sorted(x)) for x in input)
Отправляем это в Conter, получаем объект, в котором подсчитано, сколько каждый объект,
в переданном ему "списке" (вообще, итерируемом объекте) встретился: Counter(...). Если
на этом этапе вывести полученное значение, будет что-то вроде Counter({(1, 2, 3): 2,
(1, 2, 8): 1, (2, 5, 6): 1}).
Извлекаем из Counter пары (ключ, значение) (ключ - объект, значение - количество),
находим элемент с максимальным значением количества: max(Counter(...).items(), key=lambda
x: x[1]). Метод .items() как раз превращает Counter в набор пар (ключ, значение). Параметр
key=lambda x: x[1] функции max говорит, что нужно отбирать максимальное по второму
элементу каждой пары. 
"Распаковываем" полученный элемент (пару подсписок-количество) в переменные sublist
и count: sublist, count = max(...)
Выводим в виде "[список] -> количество", подсписок показываем в виде списка (а не
кортежа): print('%s -> %d' % (list(sublist), count))


Вывод:

[1, 2, 3] -> 2


Ограничения:


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


Ответ 2

Сортируем подсписки, подсчитываем их количество, получаем список и максимальное количество
его совпадений. Как-то так:

in_list = [[1, 2, 3], [2, 5, 6], [8, 2, 1], [2, 3, 1]]
print(in_list)

from collections import defaultdict
sub_list_number = defaultdict(int)

# Перебор и подсчет сортированных подсписков
for i in [sorted(i) for i in in_list]:
    # Конвертируем тип на кортеж -- он хэшируемый (только 
    # хэшируемые типы могут быть ключом словаря), в отличии от типа список
    sub_list_number[tuple(i)] += 1

# Сортировка словаря по значению -- количество найденных, подсписков
sub_list_number = sorted(sub_list_number.items(), key=lambda x: x[1])

# Достаем последний элемент -- наиболее часто встреченный список и его количество
max_number_list, number = sub_list_number[-1]
max_number_list = list(max_number_list)
print('{} -> {} шт'.format(max_number_list, number))

# python2:
# print '%s -> %s шт' % (max_number_list, number)


Результат:

[[1, 2, 3], [2, 5, 6], [8, 2, 1], [2, 3, 1]]
[1, 2, 3] -> 2 шт