python - 如何保持列表中项目“类型”的严格交替模式？

Question

给定一个字符串列表，其中每个字符串的格式为“A - something”或“B - somethingelse”，并且列表项大多在“A”数据和“B”数据之间交替，如何消除不规则性？

1. 不规则性是任何破坏 AB 模式的序列。
2. 如果有多个 A，则还应删除下一个 B。
3. 如果有多个 B，前面的 A 也应该被删除。
4. 删除这些无效序列后，应保持列表顺序。

示例： ABAB AAB ABABAB ABB ABAB AABB ABAB

在这种情况下，应该删除 AAB（参见规则 2）、ABB（参见规则 3）和 AABB。

Answer 1

我将尝试使用正则表达式返回要删除的序列索引

>>> import re
>>> data = 'ABABAABABABABABBABABAABBABAB'
>>> [(m.start(0), m.end(0)) for m in re.finditer('(AA+B+)|(ABB+)', data)]
[(4, 7), (13, 16), (20, 24)]

或剥离的结果

>>> re.sub('(AA+B+)|(ABB+)', '', data)
ABABABABABABABABAB

Answer 2

醉酒的 itertools 解决方案：

>>> s = 'ABABAABABABABABBABABAABBABAB'
>>> from itertools import groupby, takewhile, islice, repeat, chain
>>> groups = (list(g) for k,g in groupby(s))
>>> pairs = takewhile(bool, (list(islice(groups, 2)) for _ in repeat(None)))
>>> kept_pairs = (p for p in pairs if len(p[0]) == len(p[1]) == 1)
>>> final = list(chain(*chain(*kept_pairs)))
>>> final
['A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B']

（不幸的是，我现在无法考虑极端情况和尾随As 等。）

Answer 3

我会把它写成一个生成器。重复：

• 尽可能多地读A，
• 尽可能多地读B，
• 如果您已准确阅读 1 A 和 1 B，请放弃；否则忽略并继续。

此外，如果您想允许输入以A.

Answer 4

使用itertools.groupby：

from itertools import groupby

def solve(strs):
    drop_next = False
    ans = []
    for k, g in groupby(strs):
        lis = list(g)
        if drop_next:
            #if True then don't append the current set to `ans`
            drop_next = False
        elif len(lis) > 1 and k == 'A':
            #if current group contains more than 1 'A' then skip the next set of 'B'
            drop_next = True
        elif len(lis) > 1 and k == 'B':
            #if current group contains more than 1 'B' then pop the last appended item
            if ans:
                ans.pop(-1)
        else:
            ans.append(k)
    return ''.join(ans)

strs = 'ABABAABABABABABBABABAABBABAB'
print solve(strs)
#ABABABABABABABABAB