【问题标题】：Recursive combination string searching in PythonPython中的递归组合字符串搜索
【发布时间】：2023-04-02 19:59:01
【问题描述】：

我正在尝试编写一个算法，该算法将字符串 a 和较长的字符串 b 作为参数，并返回与b。 （我承认，这是对问题的错误定义。不太清楚如何措辞。希望下面的示例能够阐明我的意思。）

以下是关于输入参数的一些假设。

  1. a 和 b 中的所有字母都大写。
  2. len(a) b)
  3. 只有存在于 a 中的字母才会出现在 b 中。即 set(a) == set(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

我相当肯定我可以编写一个蛮力算法来解决这个问题，但我真正想要的是一个干净易处理的 Python 递归算法。不幸的是，我的递归编码技能并没有那么令人印象深刻。这是我目前所拥有的：

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

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

【问题讨论】：

  • 您还没有定义排列的含义。您那里的列表不是通常被认为是permutation。
  • 您似乎想要在“a”中找到“b”的排列。你能交叉检查一下吗

标签：
python
algorithm
recursion
combinations