DjangoBB LoFi version

Найти - Пользователи

Полная версия: Как проверить вхождение последовательности в список?

Начало » Python для новичков » Как проверить вхождение последовательности в список?

1 2 3

alexx11

Янв. 15, 2011 18:31:06

Isem
Вообще то там должен быть список целых чисел, а не строк.

Может там вообще только цифры от 0 до 5?

Isem
>>> f = lambda x: ‘'.join(’(%i)'%i for i in x)

Это тоже для строк не работает, выдаёт ошибку.

Isem

Янв. 15, 2011 18:42:01

alexx11
Isem
Вообще то там должен быть список целых чисел, а не строк.
Может там вообще только цифры от 0 до 5?
Isem
>>> f = lambda x: ‘'.join(’(%i)'%i for i in x)
Это тоже для строк не работает, выдаёт ошибку.

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

alexx11

Янв. 15, 2011 18:48:14

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

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

Isem
Ну а если надо для любых типов, тогда
f = lambda x:'(%s)' % ')('.join(map(repr,x))
>>> f(['b', 3]) in f(['a', 'b', 3])
True

>>> f() in f()
True

o7412369815963

Янв. 15, 2011 19:00:10

appetito
а как принято в Питоне?

например можно так:

L = set([1,2,'a',3,4,5])
S = set(['a',2,3,4])

print not (S - L)
# True

ЗЫ: не дочитал ТЗ "а S= и S= - не входят."

Isem

Янв. 15, 2011 19:15:51

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

Это вы свою реализацию имеете в виду? И что, взятие срезов списка в цикле вы считаете наиболее оптимальной реализацией?
Ну и еще раз напомню, что изначально речь шла о списках целых чисел (специально для вас: цифр от 0 до 5). Разумеется, в специальных случаях решить можно более эффективно, о чем, собственно, и шла речь.

alexx11
>>> f() in f()
True

Тут да, для строк, к сожалению, такой метод не работает.

appetito

Янв. 15, 2011 19:24:25

alexx11
appetito Вообще, да, это гораздо оптимальней будет.

len_S = len(S)
found = False;
for i in range(len(L)):
  if L[i:i+len_S] == S:
    found = True
    break

alexx11, твой вариант быстрее работает на длинных списках, str(L) - дорогая операция для большого списка ((

alexx11

Янв. 15, 2011 19:27:16

Isem
Вот решение задачи, с маленькой ошибкой, которую я даже и обсуждать не хотел, потому что сам ТС до этого дошёл:

appetito

',%s,'% str(S)[1:-1] in ',%s,'% str(L)[1:-1]

маленькая ошибка исправляется заменой в коде ‘,%s,’ на ‘,%s ,’ Приведу правильный код, что можно было оставить эти “три сосны” в покое:

',%s, '% str(S)[1:-1] in ',%s, '% str(L)[1:-1]

alexx11

Янв. 15, 2011 19:34:43

appetito
alexx11, твой вариант быстрее работает на длинных списках, str(L) - дорогая операция для большого списка ((

Что ж, приму к сведению, сам в больших объёмах ей не пользовался, поэтому видно наврал в прогнозе её оптимальности =)

Isem

Янв. 15, 2011 19:38:01

В общем случае, чтобы получить эффективный алгоритм, его надо строить на использовании метода списка index для последовательного поиска всех элементов равные первому элементу второго списка. И затем уже с этой позиции последовательно сравнивать элементы списков до первого неравенства.

alexx11

Янв. 15, 2011 20:08:35

Что ж, рас пошла такая пьянка…

def is_sublist(L, S):
	len_S_minus_one = len(S) - 1
	first_S = S[0]
	found = False;
	if not len_S_minus_one:
		if first_S in L : return True
	else:
		other_S = S[1:]
		index = 0
		while True:
			try:
				index = 1+L.index(first_S, index)
			except ValueError:
				break
			if L[index:index+len_S_minus_one] == other_S:
				found = True
				break
	return found