Тест упорядоченных подмножеств

Я хочу проверить, является ли упорядоченный набор подмножеством большего упорядоченного набора. Я использовал кортежи и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

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

 jamylak06 авг. 2012 г., 00:13
Имеет ли значение заказ?
 msampaio06 авг. 2012 г., 01:08
Спасибо, @jamylak. Я снова обновил вопрос.
 msampaio06 авг. 2012 г., 00:21
@senderle, не могли бы вы предложить лучший термин? Я хочу проверить, является ли A подмножеством упорядоченного множества B.
 jamylak06 авг. 2012 г., 00:52
Что касается вашего исходного кода, нет необходимости звонитьlistВы также можете проверить членство в генераторе, и он сохранит один прогон комбинаций.
 msampaio06 авг. 2012 г., 00:17
Да, @jamylak. Я обновил вопрос.

Ответы на вопрос(6)

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

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
 06 авг. 2012 г., 00:57
@jamylak да, спасибо, теперь выложено более быстрое решение.
 06 авг. 2012 г., 00:43
Обратите внимание, что это может стать медленным, еслиB огромен сlist.index это O (N)

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

>>> 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
 06 авг. 2012 г., 01:49
или жеfilter(functools.partial(operator.contains, a), b) и т.п.
 06 авг. 2012 г., 02:20
@gnibbler Вы бы сказали, что лучше так делать или нормально использовать специальные методы в этом случае?
 06 авг. 2012 г., 03:29
Версия специального метода, кажется, работает примерно вдвое быстрее. Понимание списка кажется самым медленным из всех.

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

>>> 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

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

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

>>> 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

>>> 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  

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

 06 авг. 2012 г., 00:58
Опс ... извините ... моя ошибка
 06 авг. 2012 г., 00:57
Элементыa может быть неправильно заказан, например.(2, 1, 0) в(0, 3, 1, 4, 2)
Решение Вопроса

чтобы отслеживать положение в 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
 14 июл. 2017 г., 23:50
Есть ли в стандарте что-нибудь, что требуетin использовать линейную итерацию и остановить момент, когда совпадение найдено? Я не могу себе представить, что это было бы сделано любым другим способом, но все еще может быть проблемой для «общего случая».
 15 июл. 2017 г., 13:02
@MadPhysicist, конечно нет.in называет основной__contains__ метод. Например, дляdict, in это конечно не линейный поиск. С другой стороны, это должен быть линейный поиск итератора - как это может означать что-то еще?
 06 авг. 2012 г., 01:32
Ух ты! Я понимаю, почему это работает, но похоже на черную магию. Поведениеin в этом случае гарантировано?

Ваш ответ на вопрос