An elegant way to collapse or expand subsequences of a list in Python?
I want to collapse or expand subsequences of a list
eg. ['A', 'B', 'D', 'E', 'H'] -> ['AB', 'DE', 'H']
and vice versa
EDIT: The above example may cause confusion. better:
eg. ['foo', 'bar', 'wtf'] <-> ['baz', 'wtf']
currently i have written some ugly code like:
while True:
for i, x in enumerate(s):
if x == 'foo' and s[i+1] == 'bar':
s[i:i+2] = 'baz'
break
else:
break
For people who ask "why do this":
I am actually working on an optimizing compiler and this is a peephole. The spelling pattern matching is a little annoying.
PS I found the following code works, but a little funny, why does the enum know our modification?
s = ['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf', 'foo', 'bar', 'wtf']
def collapse():
for i, x in enumerate(s):
if s[i] == 'foo' and s[i+1] == 'bar':
s[i:i+2] = ['baz']
def expand():
for i, x in enumerate(s):
if s[i] == 'baz':
s[i:i+1] = ['foo', 'bar']
collapse()
print s
expand()
print s
a source to share
I wouldn't call it much better, but this is a different way of doing it, and it also deals with the quirk that Justin points out. (I was more interested in finding a subsequence from a list, and I couldn't find a good function on Google)
def findsubseq(L, subseq):
if not subseq: return # just die on zero-len input
i = -1
try:
while True:
i = L.index(subseq[0], i+1)
for j in range(1, len(subseq)):
if L[i+j] != subseq[j]:
break
else:
yield i
except ValueError: pass
except IndexError: pass
def replace(target, changethis, tothis):
subseqs = [x for x in findsubseq(target, changethis)]
subseqs.reverse()
for i in subseqs:
target[i:i+len(changethis)] = tothis
def collapse():
global s
replace(s, ['foo', 'bar'], ['baz'])
def expand():
global s
replace(s, ['baz'], ['foo', 'bar'])
s = ['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf',
'foo', 'bar', 'bar', 'bar', 'foo']
print s
collapse()
print s
expand()
print s
C:\Scripts>subseq.py
['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf', 'foo', 'bar', 'bar', 'bar', 'foo']
['baz', 'wtf', 'baz', 'wtf', 'baz', 'bar', 'bar', 'foo']
['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf', 'foo', 'bar', 'bar', 'bar', 'foo']
Edit : generalized to simple substitution
a source to share
See itertools . Specifically, here's a recipe for more or less what you want (actually what I thought you wanted after your type of misleading original post!):
from itertools import tee, izip
def pairwise(iterable):
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return izip(a, b)
This will return tuples that you can join()
.
To reverse this, just join()
your final sequence and iterate over the individual elements (characters).
I will try to answer your new / real question.
a source to share
I think your enumeration path is pretty good actually. Enumerate is capable of tracking changes because it creates a generator that uses an iterator of the array that you enter. The problem I see is changing the array like this:
s = ['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf', 'foo']
then the last "foo" that does not have "bar" will throw you an exception when your code tries to look at an element outside the array. I am not sure how to fix this because my attempts were not successful.
Edit:
It may not be very elegant, but this function code collapse()
will work even in the above case:
def collapse():
i = 1
L = len(s)
while i < L:
if s[i-1] == 'foo' and s[i] == 'bar':
s[i-1:i+1] = ['baz']
L -= 1
i += 1
a source to share