Проверка наличия комбинации в списке по списку списков

Question

Если у меня есть список из списка целых чисел S: [[1,2,3],[3,4,5],[5,6,7]] и один список T: [2,3,1]. Я хочу вернуть true, если T как комбинация содержится в S. Предполагая, что каждый элемент S имеет ту же длину, что и T.

В этом случае я хочу вернуть true.

Ограничения: сортировка не предусмотрена, и примечание S имеет все уникальные списки, но в списке могут иметься повторяющиеся элементы.

Как я могу сделать это максимально эффективно. Я могу перебрать каждый элемент S, превратить его в набор и сравнить с set(T), но это кажется очень медленным, если размер S и длина каждого элемента S становятся больше.

Answer 1

Если условие без сортировки, возможно, вы захотите изучить независимую от порядка хэш-функцию для комбинаций.Мне понравились две отправные точки: (1) сумма хэшей отдельных элементов комбинации и (2) кортеж (sum(combination), product(combination)).

Answer 2

Вы можете использовать sorted:

>>> S = [[1,2,3],[3,4,5],[5,6,7]]
>>> T = [2,3,1]
>>> any(sorted(T) == sorted(x) for x in S)
True

Answer 3

Коллекции и счетчик? Он будет работать в O (n), тогда как сортировка будет выполняться примерно в O (n log n), а необработанное сравнение будет O (n²)

import collections
T = collections.Counter([2,3,1])
any(T == collections.Counter(x) for x in S)

Answer 4

Использование itertools?

from itertools import combinations
for i in combinations(t, len(t)): if i in s: return True;

Или используя отсортированный:

t = sorted(t)
for i in s: if sorted(i)==t: return True