Эффективный алгоритм, который возвращает список уникальных списков, учитывая список списков в качестве входных данных. ⇐ Python

[Anonymous]

Для python списка списков, содержащих числа, т.е. списков = [[1, 2], [2, 1], [3, 4] ], проблема состоит в том, чтобы вернуть список всех уникальных списков из входного списка. Список считается дубликатом, если его можно создать из другого списка путем изменения порядка элементов в списке. т.е. [2, 1] является дубликатом [1, 2]. Учитывая ввод [[1, 2], [2, 1], [3, 4] ] , вывод должен быть [[1, 2], [3, 4]] . Любое изменение порядка [[1, 2], [3, 4]] также является правильным, т.е. [1, 2], [4, 3]],
Мой подход заключается в том, чтобы сначала отсортировать все списки во входном списке, преобразовать списки в кортежи, использовать заданную структуру данных для фильтрации повторяющихся кортежей и, наконец, преобразовать уникальные кортежи обратно в списки. Временная сложность сортировки всех списков равна O(m*nlogn), где m — количество списков, а n — размер каждого списка (при условии, что списки одинакового размера). Преобразование списков в кортежи занимает время O(mn), создание набора из кортежей занимает O(mn), преобразование набора уникальных кортежей обратно в списки также занимает O(mn) делая общую временную сложность O(mnlogn + mn + mn + mn) = O(mnlogn).
Можем ли мы сделать что-нибудь лучше, чем O(mnlogn)?
Код:
def find_unique(lists):
sorted_lists = [ sorted(lst) for lst in lists]
tuples = [tuple(lst) for lst in sorted_lists]
unique_tuples = set(tuples)
return list(unique_tuples)


Подробнее здесь: https://stackoverflow.com/questions/792 ... f-of-lists