DjangoBB LoFi version

Полная версия: Количество вхождений списка А в список Б

Начало » Python для новичков » Количество вхождений списка А в список Б

1 2

Romanus

Июль 23, 2018 18:16:47

Всем привет.
Продолжаю постигать основы питона и решать какие-то задачки.

Задача:
Есть список А = {1, 2}
И список Б = {0, 1, 2, 3, 1, 2, 1}

Нужно найти, сколько полных раз список А входит в список Б. Т.е. не отдельные элементы, а именно последовательности (прямая + обратная).

В данном случае: 2 полных вхождения и 1 кусок.

Решение:
Пока в голове даже не особо складывается. Видел, что есть метод list(set(a) & set(b)) - но он находит именно пересечения (т.е. одинаковые элементы) - это не то.

Думал, делать список который будет брать каждый элемент Б и искать в нем либо А(1) либо А(2), если нашел - ищет оставшийся в следующем элементе - если ложь - искать дальше, если истина - записываем +1 вхождение (это же словарь нужно делать, верно?) для списка А.

Но не уверен, что это разумное решение. Буду признателен подсказкам.

vic57

Июль 23, 2018 18:29:23

 >>> a =[1,2,3,4,5,6,2,3,4]
>>> b = [2,3,4]
>>> while a:
	print(b == a[:len(b)])
	a = a[1:]
False
True
False
False
False
False
True
False
False
>>>

или так

 >>> for i in range(len(a)):
	print(i,b == a[i:i + len(b)])
	
0 False
1 True
2 False
3 False
4 False
5 False
6 True
7 False
8 False

Romanus

Июль 23, 2018 19:08:40

Круто. Я правильно понимаю строки?

 a =[1,2,3,4,5,6,2,3,4]
b = [2,3,4]
while a: # пока a существует?
	print(b == a[:len(b)]) # вхождение последовательности в определенном порядке
	a = a[1:] # присваиваем а значения от 1 элемента списка? Т.е. аля сдвиг вправо?

Вхождения не подряд (т.е. 2,4,3 или 4,3,2 или 3,4,2 или 3,2,4) можно в лоб определять, а можно просто делать какую-то рандомизацию с перебором всех вариантов и в цикле так же искать?

Или всё не верно понимаю?

py.user.next

Июль 23, 2018 19:48:30

  
>>> lst1 = [0, 1, 2, 3, 1, 2, 1]
>>> lst2 = [1, 2]
>>> 
>>> n = 0
>>> icur = 0
>>> ilast = len(lst2) - 1
>>> for item in lst1:
...     if lst2[icur] == item:
...         if icur == ilast:
...             n += 1
...             icur = 0
...         else:
...             icur += 1
... 
>>> n
2
>>>

  
>>> def f(lst, sublst):
...     n = 0
...     icur, ilast = 0, len(sublst) - 1
...     for item in lst:
...         if sublst[icur] == item:
...             if icur == ilast:
...                 n += 1
...                 icur = 0
...             else:
...                 icur += 1
...     return n
... 
>>> 
>>> f([0, 1, 2, 3, 1, 2, 1], [1, 2])
2
>>> f([], [1, 2])
0
>>> f([1], [1, 2])
0
>>> f([1, 2], [1, 2])
1
>>> f([1, 2, 1], [1, 2])
1
>>> f([1, 2, 1, 2], [1, 2])
2
>>>

vic57

Июль 23, 2018 20:01:14

сдвиг влево.
для сочетаний можно использовать itertools

 >>> from itertools import permutations
>>> a = [1,2,3,4,5,6,2,3,4]
>>> b = [2,3,4]
>>> lp = [list(i) for i in list(permutations(b))]
>>> lp
[[2, 3, 4], [2, 4, 3], [3, 2, 4], [3, 4, 2], [4, 2, 3], [4, 3, 2]]
>>> ln = len(b)
>>> for i in range(len(a)):
	if a[i:i+ln] in lp: print(i,a[i:i+ln])
	
1 [2, 3, 4]
6 [2, 3, 4]
>>>

Rodegast

Июль 23, 2018 20:11:31

А ещё списки можно перевести в строки…

 >>> a = [1,2]
>>> b = [0, 1, 2, 3, 1, 2, 1]
>>> ",".join(map(str, b)).count(",".join(map(str, a)))
2

vic57

Июль 23, 2018 20:29:17

тогда уж лучше set - типонезависимо

 >>> a = [1,2,3,'1','2',3]
>>> b = [3,'2','1']
>>> s = set(b)
>>> ln = len(b)
>>> for i in range(len(a)):
	l = a[i:i+ln]
	if set(l) == s: print(i,l)
	
2 [3, '1', '2']
3 ['1', '2', 3]
>>>

py.user.next

Июль 23, 2018 20:43:16

Rodegast
А ещё списки можно перевести в строки…
 >>> a = [1,2]
>>> b = [0, 1, 2, 3, 1, 2, 1]
>>> ",".join(map(str, b)).count(",".join(map(str, a)))
2

Только надо не забывать, что это считается ламеризмом, так как подобные хаки являются источником непредсказуемых ошибок.

Пример

  
>>> a = [1,2]
>>> b = [0, 1, 2, 3, 1, 2, 1]
>>> ",".join(map(str, b)).count(",".join(map(str, a)))
2
>>> 
>>> 
>>> a = ['1,2']
>>> b = [0, 1, 2, 3, 1, 2, 1]
>>> ",".join(map(str, b)).count(",".join(map(str, a)))
2
>>>

Romanus

Июль 23, 2018 21:17:53

Всем спасибо.
1) В Питоне куча пакетов, как узнать какой можно использовать? Это чисто личный опыт? Или есть какая-то краткая сводка по каждому пакету?
2) Я попутно с ковырянием различных задач и примеров читаю Лутц М. - Изучаем Python (4-е издание)- 2011г (посоветовали). Смущает 2011 год или не обращать внимание на это? Может есть лучше и детальнее литература?
3) Для работы с морфологией есть 2 варианта (насколько я понял): Mystem и Pymorphy2. У них есть различия (сделал для примера токенизацию и некоторые слова они по-разному лемматизируют). Но моя выборка - ничто в сравнении с общей картиной. Может быть имели опыт работы с ними?

P.S. За itertools отдельное спасибо, крутая штука.

vic57

Июль 23, 2018 22:11:10

я обычно иду от задачи - что нужно сделать и как
по пакетам можно узнать тут
https://pypi.org/search/
книг неплохая подборка тут
http://forcoder.ru/python/