Проверьте наличие разреженного списка в Python

Ответ 1

Если вы уверены, что ваши входы будут содержать только цифры 0 и 1, вы можете преобразовать их в строки:

def sublistExists(list1, list2):
    return ''.join(map(str, list2)) in ''.join(map(str, list1))

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

Если эффективность очень важна, вы можете посмотреть на алгоритм поиска Boyer-Moore, адаптированный для работы над списками.

Наивный поиск имеет O (n * m) наихудший случай, но может быть подходящим, если вы не можете использовать преобразование в трюк строки, и вам не нужно беспокоиться о производительности.

Ответ 2

Давайте получим немного функциональный, не так ли?:)

def contains_sublist(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1))

Обратите внимание, что any() остановится при первом совпадении в подстроке внутри lst - или завершится сбой, если нет совпадения после O (m * n) ops

Ответ 3

Нет функции, которую я знаю

def sublistExists(list, sublist):
    for i in range(len(list)-len(sublist)+1):
        if sublist == list[i:i+len(sublist)]:
            return True #return position (i) if you wish
    return False #or -1

Как отметил Марк, это не самый эффективный поиск (это O (n * m)). К этой проблеме можно подойти почти так же, как поиск строк.

Ответ 4

Эффективный способ сделать это - использовать алгоритм Boyer-Moore, как предполагает Марк Байерс. Я уже делал это здесь: Boyer-Moore ищет список для под-списка в Python, но здесь будет вставлять код. Он основан на статье в Википедии.

Функция search() возвращает индекс искаженного под-списка или -1 при ошибке.

def search(haystack, needle):
    """
    Search list `haystack` for sublist `needle`.
    """
    if len(needle) == 0:
        return 0
    char_table = make_char_table(needle)
    offset_table = make_offset_table(needle)
    i = len(needle) - 1
    while i < len(haystack):
        j = len(needle) - 1
        while needle[j] == haystack[i]:
            if j == 0:
                return i
            i -= 1
            j -= 1
        i += max(offset_table[len(needle) - 1 - j], char_table.get(haystack[i]));
    return -1


def make_char_table(needle):
    """
    Makes the jump table based on the mismatched character information.
    """
    table = {}
    for i in range(len(needle) - 1):
        table[needle[i]] = len(needle) - 1 - i
    return table

def make_offset_table(needle):
    """
    Makes the jump table based on the scan offset in which mismatch occurs.
    """
    table = []
    last_prefix_position = len(needle)
    for i in reversed(range(len(needle))):
        if is_prefix(needle, i + 1):
            last_prefix_position = i + 1
        table.append(last_prefix_position - i + len(needle) - 1)
    for i in range(len(needle) - 1):
        slen = suffix_length(needle, i)
        table[slen] = len(needle) - 1 - i + slen
    return table

def is_prefix(needle, p):
    """
    Is needle[p:end] a prefix of needle?
    """
    j = 0
    for i in range(p, len(needle)):
        if needle[i] != needle[j]:
            return 0
        j += 1    
    return 1

def suffix_length(needle, p):
    """
    Returns the maximum length of the substring ending at p that is a suffix.
    """
    length = 0;
    j = len(needle) - 1
    for i in reversed(range(p + 1)):
        if needle[i] == needle[j]:
            length += 1
        else:
            break
        j -= 1
    return length

Вот пример из вопроса:

def main():
    list1 = [1,0,1,1,1,0,0]
    list2 = [1,0,1,0,1,0,1]
    index = search(list1, [1, 1, 1])
    print(index)
    index = search(list2, [1, 1, 1])
    print(index)

if __name__ == '__main__':
    main()

Вывод:

2
-1

Ответ 5

def sublistExists(x, y):
  occ = [i for i, a in enumerate(x) if a == y[0]]
  for b in occ:
      if x[b:b+len(y)] == y:
           print 'YES-- SUBLIST at : ', b
           return True
      if len(occ)-1 ==  occ.index(b):
           print 'NO SUBLIST'
           return False

list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]

#should return True
sublistExists(list1, [1,1,1])

#Should return False
sublistExists(list2, [1,1,1])

Ответ 6

Вот способ, который будет работать для простых списков, которые немного менее хрупкие, чем у Марка

def sublistExists(haystack, needle):
    def munge(s):
        return ", "+format(str(s)[1:-1])+","
    return munge(needle) in munge(haystack)

Ответ 7

Можно также вставить рекурсивную версию решения @NasBanov

def foo(sub, lst):
    '''Checks if sub is in lst.

    Expects both arguments to be lists
    '''
    if len(lst) < len(sub):
        return False
    return sub == lst[:len(sub)] or foo(sub, lst[1:])

Ответ 8

def sublist(l1,l2):
  if len(l1) < len(l2):
    for i in range(0, len(l1)):
      for j in range(0, len(l2)):
        if l1[i]==l2[j] and j==i+1:
        pass
      return True
  else:
    return False

Ответ 9

Если я понимаю это правильно, у вас есть больший список, например:

list_A= ['john', 'jeff', 'dave', 'shane', 'tim']

тогда есть другие списки

list_B= ['sean', 'bill', 'james']

list_C= ['cole', 'wayne', 'jake', 'moose']

а затем добавьте списки B и C в список A

list_A.append(list_B)

list_A.append(list_C)

поэтому, когда я печатаю list_A

print (list_A)

я получаю следующий вывод

['john', 'jeff', 'dave', 'shane', 'tim', ['sean', 'bill', 'james'], ['cole', 'wayne', 'jake', 'moose']]

теперь, когда я хочу проверить, существует ли сублиант:

for value in list_A:
    value= type(value)
    value= str(value).strip('<>').split()[1]
    if (value == "'list'"):
        print "True"
    else:
        print "False"

это даст вам "Истину", если у вас есть подсписок внутри большего списка.

Ответ 10

Просто создайте наборы из двух списков и используйте функцию issubset:

def sublistExists(big_list, small_list):
    return set(small_list).issubset(set(big_list))