python - Python中的递归组合字符串搜索

Question

我正在尝试编写一种算法，该算法将字符串 a 和更长的字符串 b 作为参数，并返回与中的字母对应的所有可能的有序索引组合b。 (我承认，这是对问题的一个糟糕定义。不太确定如何措辞。希望下面的示例能够阐明我的意思。)

这里是关于输入参数的一些假设。

1. a 和 b 中的所有字母均大写。
2. len(a) < len(b)
3. 只有存在于a 中的字母才会出现在b 中。即设置(a)==设置(b)
4. a 和 b 都允许有重复的字母。

例子:

如果 a = "SLSQ"和 b = "SQLSSQLSQ"，那么结果将如下所示:

result = [
[0,2,3,5],
[0,2,3,8],
[0,2,4,5],
[0,2,4,8],
[0,2,7,8],
[0,6,7,8],
[3,6,7,8],
[4,6,7,8]]

另一种看待它的方式；对于上面的例子，我明确地写出了递归算法的结果。数字是b的字母索引。

0123456789
SQLSSQLSQS      SLSQ
S LS Q      ->  0235
S LS    Q   ->  0238
S L SQ      ->  0245
S L S   Q   ->  0248
S L    SQ   ->  0278
S     LSQ   ->  0678
   S  LSQ   ->  3678
    S LSQ   ->  4678

我相当确定我可以编写一个强力算法来解决这个问题，但我真正想要的是一个干净易处理的 pythonic 递归算法。不幸的是，我的递归编码技巧并不令人印象深刻。这是我目前所拥有的:

def recurse(a_str, b_str, res):

    if len(a_str) == 0:
        return _, _, res
    for token in b_str:
        if token == a_str[0]:
            _ = a_str[0]
            _, _, res = recurse(a_str[1:], b_str, res)
        else:
            _, _, res = recurse(a_str, b_str[1:], res)
    return _, _, res

“_”只是占位符，直到我弄清楚下一步该做什么。我的脑袋疼。任何建议将不胜感激。

Answer 1

这是a 和b 的递归版本跟踪索引，如ai 和bi

def recurse(a_str, b_str, ai=0, bi=0):
    if not a_str:
        return
    if ai < len(a_str):
        b_lim = len(b_str) - len(a_str) + ai + 1
        for i in range(bi, b_lim):
            if a_str[ai] == b_str[i]:
                for r in recurse(a_str, b_str, ai+1, i+1):
                    yield (i,) + r
    else:
        yield ()

---

list(recurse(a, b))
[(0, 2, 3, 5),
 (0, 2, 3, 8),
 (0, 2, 4, 5),
 (0, 2, 4, 8),
 (0, 2, 7, 8),
 (0, 6, 7, 8),
 (3, 6, 7, 8),
 (4, 6, 7, 8)]