# inner sublist positions ?

Discussion in 'Python' started by Bernard A., Apr 20, 2005.

1. ### Bernard A.Guest

hello,

while trying to play with generator, i was looking for an idea to get
the position of a inner list inside another one, here is my first idea
:
- first find position of first inner element,
- and then see if the slice starting from here is equal to the inner
->

>>> def subPositions(alist, innerlist):

if innerlist == []:
return
first, start = innerlist[0], 0
while 1:
try:
p = alist[start:].index(first)
except ValueError:
break # or should i better use return ?
start = start + p
if alist[start: start + len(innerlist)] == innerlist:
yield start, start + len(innerlist)
start += 1

>>> list(subPositions(range(5) + range(5), [2,3]))

[(2, 4), (7, 9)]

maybe have you some better / faster ideas / implementations ? or even
a more pythonic to help me learning that

game2 => how can i imagine a way to have the inclusion test rather
be a test upon a regular expression ? i mean instead of checking for
an inner list, rather checking for an "inner regular expression"
matching upon consecutives items of a list ? (btw it isn't still not
really clear in my own mind, but it looks like ideas from here are
always clever one, it may help

best,

Bernard A., Apr 20, 2005

2. ### Steven BethardGuest

Bernard A. wrote:
> hello,
>
> while trying to play with generator, i was looking for an idea to get
> the position of a inner list inside another one, here is my first idea
> :
> - first find position of first inner element,
> - and then see if the slice starting from here is equal to the inner
> ->
>
>>>>def subPositions(alist, innerlist):

>
> if innerlist == []:
> return
> first, start = innerlist[0], 0
> while 1:
> try:
> p = alist[start:].index(first)
> except ValueError:
> break # or should i better use return ?
> start = start + p
> if alist[start: start + len(innerlist)] == innerlist:
> yield start, start + len(innerlist)
> start += 1
>
>
>
>>>>list(subPositions(range(5) + range(5), [2,3]))

>
> [(2, 4), (7, 9)]
>
> maybe have you some better / faster ideas / implementations ? or even
> a more pythonic to help me learning that

I don't know if this is any faster, but you could try:

py> def indexes(lst, sublist):
.... sublen = len(sublist)
.... for i in range(len(lst)):
.... if lst[i:i+sublen] == sublist:
.... yield i, i+sublen
....
py> list(indexes(range(5) + range(5), [2, 3]))
[(2, 4), (7, 9)]

Use the timeit module to see if it's any faster. Also, in your version
you should probably use
p = alist.index(first, start)
p = alist[start:].index(first)
so you don't make so many new lists.

STeVe

Steven Bethard, Apr 21, 2005

3. ### tiissaGuest

Bernard A. wrote:
> maybe have you some better / faster ideas / implementations ? or even
> a more pythonic to help me learning that

You may want to look at string matches algorithm (a good review: [1]).
In particular there are classics like Boyer-Moore and some involving
minimal automatons similar to your regular expression ideas.

[1] http://www-igm.univ-mlv.fr/~lecroq/string/index.html

tiissa, Apr 21, 2005