在Python中优雅地折叠或展开列表的子序列的方法？

Question

我想要折叠或展开列表中的子序列

比如说 ['A', 'B', 'D', 'E', 'H'] -> ['AB', 'DE', 'H'] 以及反向操作

编辑：上面的例子可能会让人误解，下面这个更好：

比如说 ['foo', 'bar', 'wtf'] <-> ['baz', 'wtf']

目前我写了一些很丑的代码，比如：

while True:
  for i, x in enumerate(s):
    if x == 'foo' and s[i+1] == 'bar':
      s[i:i+2] = 'baz'
      break
  else:
    break

对于那些问“为什么要这样做”的人：

其实我在做一个优化编译器，这部分是窥视窗口优化。写模式匹配有点烦。

附言：我发现下面的代码可以工作，但有点荒谬，为什么枚举能知道我们的修改呢？

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

Answer 1

我觉得你用 enumerate 的方法其实挺不错的。enumerate 可以跟踪你对数组的修改，因为它会创建一个生成器，利用你输入的数组的迭代器。不过，我看到的问题是，如果你把数组改成这样：

s = ['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf', 'foo']

那么最后一个没有 'bar' 的 'foo' 在你的代码尝试查看数组末尾之后的项目时，会出现异常。我现在还不太确定怎么解决这个问题，因为我尝试过的方法都没有成功。

编辑：

虽然可能不是很优雅，但这个 collapse() 函数的代码在上面的情况下也能正常工作：

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

Answer 2

可以看看 itertools 这个库。具体来说，这里有一个大致符合你需求的做法（其实是我根据你最初有点误导性的提问，猜测你想要的东西！）：

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)

这个做法会返回一些元组，你可以用 join() 把它们连接起来。

如果想要恢复原来的样子，只需用 join() 把最终的序列连接起来，然后逐个遍历里面的字符。

我会努力给你一个针对你新问题的答案。

Answer 3

我不觉得这个方法比之前的好多少，但它是一种不同的做法，而且也解决了Justin提到的那个小问题。（我更想找到一个列表中的子序列，但在谷歌上找不到合适的函数）

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']

编辑: 把它简单化成一个普通的替换函数