Вопрос по python – Есть ли встроенный Python для определения, содержит ли итерация определенную последовательность?

5

Например, что-то вроде:

>>> [1, 2, 3].contains_sequence([1, 2])
True
>>> [1, 2, 3].contains_sequence([4])
False

Я знаю чтоin Оператор может сделать это для строк:

>>> "12" in "123"
True

Но я ищу что-то, что работает с итерациями.

Ааа, обратный трек не требуется! Jon Clements♦
Да, но встретил некоторых безумных клиентов :), т. Е. "Несомненно, вы можете изменить нашу базу данных на 57 таблиц с 200 миллионами строк до завтра" & quot; :) Jon Clements♦
Может ли последовательность появиться где-нибудь внутри другой последовательности? Jon Clements♦
Да & # x2014; операция, которую я имею в виду, идентична поведениюin оператор на строках, за исключением общих итераций. David Wolever
Ладно, только что понял, что это уже после 5 утра, и мне нужно немного подготовиться к работе, и побыть на ПК всю ночь :( Так что, если вы не получите приемлемый ответ, он будет хихикать сзади моего коричневого цвета, но в остальном с нетерпением жду встречи с ним. GL Jon Clements♦

Ваш Ответ

8   ответов
2

вы можете использовать наборы (встроенные):

>>> set([1,2]).issubset([1,2,3])
True
>>> set([4]).issubset([1,2,3])
False

Иначе:

def is_subsequence(sub, iterable):
    sub_pos, sub_len = 0, len(sub)
    for i in iterable:
        if i == sub[sub_pos]:
            sub_pos += 1
            if sub_pos >= s,ub_len:
                return True
        else:
            sub_pos = 0
    return False

>>> is_subsequence([1,2], [0,1,2,3,4])
True
>>> is_subsequence([2,1], [0,1,2,3,4]) # order preserved
False
>>> is_subsequence([1,2,4], [0,1,2,3,4])
False

Этот работает с любым итератором.

@mgilson, спасибо за комментарий! Был добавлен другой вариант - он работает с итерациями и сохраняет порядок подпоследовательности.
Это не сохранит порядок.set([1,2]).issubset([2,1,3]) #True???
3

ыми способами.Вот рецепт это делает это, а также дает вам позицию подпоследовательности в содержащей последовательности:

def _search(forward, source, target, start=0, end=None):
    """Naive search for target in source."""
    m = len(source)
    n = len(target)
    if end is None:
        end = m
    else:
        end = min(end, m)
    if n == 0 or (end-start) < n:
        # target is empty, or longer than source, so obviously can't be found.
        return None
    if forward:
        x = range(start, end-n+1)
    else:
        x = range(end-n, start-1, -1)
    for i in x:
        if source[i:i+n] == target:
            return i
    return None
Спасибо за ответ на фактический вопрос ("есть ли встроенный") перед предоставлением реализации. David Wolever
4

https://stackoverflow.com/a/6822773/24718 изменено, чтобы использовать список.

from itertools import islice

def window(seq, n=2):
    """
    Returns a sliding window (of width n) over data from the iterable
    s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   
    """
    it = iter(seq)
    result = list(islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + [elem]
        yield result

def contains_sequence(all_values, seq):
    return any(seq == current_seq for current_seq in window(all_values, len(seq)))            

test_iterable = [1,2,3]
search_sequence = [1,2]

result = contains_sequence(test_iterable, search_sequence)
2

нет способа сделать это. Вы можете выполнить свою собственную функцию довольно легко, но я сомневаюсь, что это будет очень эффективно.

>>> def contains_seq(seq,subseq):
...     #try: junk=seq[:]
...     #except: seq=tuple(seq)
...     #try: junk=subseq[:]
...     #except: subseq=tuple(subseq)
...     ll=len(subseq)
...     for i in range(len(seq)-ll):  #on python2, use xrange.
...         if(seq[i:i+ll] == subseq):
...             return True
...     return False
...
>>> contains_seq(range(10),range(3)) #True
>>> contains_seq(range(10),[2,3,6]) #False

Обратите внимание, что это решение не работает с объектами типа генератора (оно работает только с объектами, которые можно нарезать). Вы можете проверитьseq чтобы увидеть, является ли это нарезанным, прежде чем продолжить и привести кtuple если он не нарезанный - но тогда вы избавляетесь от преимуществ нарезки. Вы можете переписать его, чтобы проверять один элемент за раз вместо использования нарезки, но я чувствую, что производительность пострадает еще больше.

@Junuxx - Да, это то, что я имел в виду. Благодарю.
@EdwardLoper - это правда. Я действительно думал об этом. строго говоря, я бы посчиталxrange бытьiterable и неsequence ( docs.python.org/glossary.html ). Лично я думаю, что эта функция, вероятно, должна поддерживать последовательности только по причинам, которые я добавил выше.
Спасибо за ответ на фактический вопрос ("есть ли встроенный") перед предоставлением реализации. David Wolever
@mgilson: разве вы не имеете в виду "на Python 2", используйте xrange "?
Это требует какseq а такжеsubseq быть похожим на последовательность (а не просто повторяемым) - т.е.contains_seq(xrange(10), range(3)) не будет работать.
1

Deque кажется полезным здесь:


def contains(it, seq):
    seq = deque(seq)
    deq = deque(maxlen=len(seq))
    for p in it:
        deq.append(p)
        if deq == seq:
            return True
    return False

Обратите внимание, что это принимает произвольные итерации для обоих аргументов (не требуется разрезание).

0

import itertools as it

def contains(seq, sub):
    seq = iter(seq)
    o = object()
    return any(all(i==j for i,j in zip(sub, it.chain((n,),seq, 
                                      (o for i in it.count())))) for n in seq)

этоdo not require any extra lists (если вы используетеit.izip или Py3k).

>>> contains([1,2,3], [1,2])
True
>>> contains([1,2,3], [1,2,3])
True
>>> contains([1,2,3], [2,3])
True
>>> contains([1,2,3], [2,3,4])
False

Дополнительные очки, если у вас нет проблем с чтением. (Это делает работу, но реализация не должна восприниматься слишком серьезно). ;)

2

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

def contains_seq(iterable, seq):
    """
    Returns true if the iterable contains the given sequence.
    """
    # The following clause is optional -- leave it if you want to allow `seq` to
    # be an arbitrary iterable; or remove it if `seq` will always be list-like.
    if not isinstance(seq, collections.Sequence):
        seq = tuple(seq)

    if len(seq)==0: return True # corner case

    partial_matches = []
    for elt in iterable:
        # Try extending each of the partial matches by adding the
        # next element, if it matches.
        partial_matches = [m+1 for m in partial_matches if elt == seq[m]]
        # Check if we should start a new partial match
        if elt==seq[0]:
            partial_matches.append(1)
        # Check if we have a complete match (partial_matches will always
        # be sorted from highest to lowest, since older partial matches 
        # come before newer ones).
        if partial_matches and partial_matches[0]==len(seq):
            return True
    # No match found.
    return False
hasattr проверка будет лучше записана как:if not isinstance(seq, collections.Sequence) (хотя это имеет немного другую семантику, поэтому вы также можете проверитьcollections.Mapping). И это действительно должно идтиbefore проверка на пустую последовательность.
hasattr бит был вставлен, чтобы позволитьseq («игла») быть любой произвольно повторяемой, если это желательно, например,contains_seq(xrange(100), xrange(3,8)), Если известно, что игла подобна списку, то от этого можно избавиться.
Я не думаю, что буду использоватьhasattr немного. Вы получаете возможность проверитьsets и, возможно, некоторые определенные пользователем объекты, но я бы не ожидал, что объект не поддерживает__getitem__ быть заказанным. Я думаю, что лучше заставить пользователя явно привести к другому объекту - хотя я полагаю, что он позволяет использовать генераторы и т. Д. (Но отбрасывает все их преимущества) ...
-2

а затем сделать сопоставление на нем

full_list = " ".join([str(x) for x in [1, 2, 3]])
seq = " ".join([str(x) for x in [1, 2]])
seq in full_list
Это будет работать только в том случае, если элементы могут быть преобразованы в строки. David Wolever
Да, но пример только пример. И заголовок, и последний абзац проясняют, что я заинтересован в общих итерациях. Кроме того, предложенные вами методы неверны, даже если входные данные состоят только из целых чисел: рассмотрим случай, когда я хочу определить,[12] содержит последовательность[1] (или определить,["foobar"] содержит["foo"]). David Wolever
Ах, это правда, я не думал ни о каком из этих случаев
Это также даст Истину для ввода['list','one','list','two']поиск для['list one','list two'], Хотя это редкий случай, все же стоит упомянуть.
Да, но приведенный пример был для целых чисел, которые довольно легко можно преобразовать в строку. Мало того, что использование str.join и затем оператора in является очень эффективным способом сделать это, поскольку str.join - эффективная операция по сравнению с итерацией списка.

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