Сравнение (==) двух неотсортированных массивов

Нужна ваша консультация)

Есть ли алгоритм позволяющий сравнить (равно или нет) содержимое двух неотсортированных массивов?

Т.е. [3, 2, 1] == [1, 2, 3], но можно ли получить в таком случае True, не сортируя эти массивы заранее?


Ответы (3 шт):

Автор решения: Alex Fox

Нашел библиотеку fuzzywuzzy

Конкретно для этой задачи ответ:

    fuzzy.token_sort_ratio([3, 2, 1], [1, 2, 3])

Вернет: 100%

→ Ссылка
Автор решения: Daniil Molotkov

Можно использовать встроенный модуль collections,

import collections 

l1 = [10, 99, 20, 30, 40, 50]
l2 = [10, 20, 30, 99, 50, 40]


if collections.Counter(l1) == collections.Counter(l2):
    print ("Списки l1 и l2 одинаковые")
else:
    print ("Списки l1 и l2 неодинаковые")
→ Ссылка
Автор решения: CrazyElf

Сначала нужно ответить на вопрос "а вы с какой целью интересуетесь?" Пример целей:

  • затратить наименьшее кол-во усилий
  • экономия памяти
  • наиболее быстрый алгоритм

И решение в каждом случае будет разное. Например, в третьем случае имеет смысл сначала сравнить длины списков, если они разные - то ответ очевидно False. А если длины одинаковые, то можно посчитать (через Counter или через словарь) элементы первого списка, а потом идти по второму списку и уменьшать ранее полученные счётчики, если вдруг какой-нибудь из счётчиков упадёт меньше 0, то опять же мы досрочно получаем ответ False.

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

Ну а про первый вариант уже написали сравнить два Counter между собой.

→ Ссылка