Вопрос по subset, itertools, tuples, python – Тест упорядоченных подмножеств

5

Я хочу проверить, является ли упорядоченный набор подмножеством большего упорядоченного набора. Я использовал кортежи иitertools.combinations:

def subset_test(a, b):
    return a in itertools.combinations(b, len(a))

Например,

>>> subset_test((0, 1, 2), (0, 3, 1, 4, 2))
True
>>> subset_test((0, 1, 2), (0, 3, 2, 4, 1))
False

Это работает, но медленно, когда я тестирую большие кортежи.

Да, @jamylak. Я обновил вопрос. msampaio
Имеет ли значение заказ? jamylak
Что касается вашего исходного кода, нет необходимости звонитьlistВы также можете проверить членство в генераторе, и он сохранит один прогон комбинаций. jamylak
Спасибо, @jamylak. Я снова обновил вопрос. msampaio
@senderle, не могли бы вы предложить лучший термин? Я хочу проверить, является ли A подмножеством упорядоченного множества B. msampaio

Ваш Ответ

6   ответов
1

Это должно начать вас

>>> A = (0, 1, 2)
>>> B = (0, 3, 1, 4, 2)
>>> b_idxs = {v:k for k,v in enumerate(B)}
>>> idxs = [b_idxs[i] for i in A]
>>> idxs == sorted(idxs)
True

Если понимание списка бросаетKeyErrorтогда, очевидно, ответ такжеFalse

-1

>>> a = (0, 1, 2)
>>> b = (0, 3, 1, 4, 2)
>>> set(a).issubset(set(b))
True

В этом примере a и b имеют упорядоченные и уникальные элементы, и он проверяет, является ли a подмножеством b. Это ты хочешь?

РЕДАКТИРОВАТЬ:

Согласно @Marcos da Silva Sampaio: «Я хочу проверить, является ли A подмножеством упорядоченного множества B.»

Это не относится к случаю:

>>> a = (2, 0, 1)
>>> b = (0, 3, 1, 4, 2)
>>> set(b).issuperset(a)
True  

В этом случае порядок не имеет значения.

Элементыa может быть неправильно заказан, например.(2, 1, 0) в(0, 3, 1, 4, 2)
Опс ... извините ... моя ошибка
1

Здесь подход линейного времени (в самом длинном наборе), который не требует хеширования. Он использует тот факт, что, поскольку оба набора упорядочены, более ранние элементы в наборе не требуют повторной проверки:

>>> def subset_test(a, b):
...     b = iter(b)
...     try:
...         for i in a:
...             j = b.next()
...             while j != i:
...                 j = b.next()
...     except StopIteration:
...         return False
...     return True
... 

Несколько тестов:

>>> subset_test((0, 1, 2), (0, 3, 1, 4, 2))
True
>>> subset_test((0, 2, 1), (0, 3, 1, 4, 2))
False
>>> subset_test((0, 1, 5), (0, 3, 1, 4, 2))
False
>>> subset_test((0, 1, 4), (0, 3, 1, 4, 2))
True

Я уверен, что это правильно - дайте мне знать, если у вас возникнут проблемы.

12

чтобы отслеживать положение в B

>>> A = (0, 1, 2)
>>> B = (0, 3, 1, 4, 2)
>>> b_iter = iter(B)
>>> all(a in b_iter for a in A)
True
Ух ты! Я понимаю, почему это работает, но похоже на черную магию. Поведениеin в этом случае гарантировано?
Есть ли в стандарте что-нибудь, что требуетin использовать линейную итерацию и остановить момент, когда совпадение найдено? Я не могу себе представить, что это было бы сделано любым другим способом, но все еще может быть проблемой для «общего случая».
@MadPhysicist, конечно нет.in называет основной__contains__ метод. Например, дляdict, in это конечно не линейный поиск. С другой стороны, это должен быть линейный поиск итератора - как это может означать что-то еще?
3

Простой способ сделать это

>>> a = (0, 1, 2)
>>> b = (0, 3, 1, 4, 2)
>>> filter(set(a).__contains__, b) == a
True

Для большей эффективности использованияitertools

>>> from itertools import ifilter, imap
>>> from operator import eq
>>> all(imap(eq, ifilter(set(a).__contains__, b), a))
True
Версия специального метода, кажется, работает примерно вдвое быстрее. Понимание списка кажется самым медленным из всех.
@gnibbler Вы бы сказали, что лучше так делать или нормально использовать специальные методы в этом случае?
или жеfilter(functools.partial(operator.contains, a), b) и т.п.
1

но я имею в виду более быстрый, я надеюсь, что скоро будет:

def is_sorted_subset(A, B):
    try:
      subset = [B.index(a) for a in A]
      return subset == sorted(subset)
    except ValueError:
      return False

Обновление: здесь я обещал быстрее.

def is_sorted_subset(A, B):
  max_idx = -1
  try:
    for val in A:
      idx = B[max_idx + 1:].index(val)
      if max(idx, max_idx) == max_idx:
        return False
      max_idx = idx
  except ValueError:
    return False
  return True
Обратите внимание, что это может стать медленным, еслиB огромен сlist.index это O (N)
@jamylak да, спасибо, теперь выложено более быстрое решение.

Похожие вопросы