Python递归通过滑动窗口拆分字符串

Question

最近，我遇到了一个有趣的编码任务，涉及将字符串拆分为具有给定 K 限制大小的多个排列。

例如：

s = "iamfoobar"

k = 4  # the max number of the items on a list after the split

s可以拆分为以下组合

[

    ["i", "a", "m", "foobar"],

    ["ia", "m", "f", "oobar"],

    ["iam", "f", "o", "obar"]

# etc

]

我试图弄清楚如何使用快速递归函数来做到这一点，但我无法让它工作。

我已经试过了，但似乎没有用

def sliding(s, k):

    if len(s) < k:

        return []

    else:

        for i in range(0, k):

            return [s[i:i+1]] + sliding(s[i+1:len(s) - i], k)

print(sliding("iamfoobar", 4))

只有这个

['i', 'a', 'm', 'f', 'o', 'o']

Answer 1

您的第一个主要问题是，尽管您使用循环，但您会立即返回一个列表。因此，无论您如何修复周围的一切，您的输出都永远不会符合您的预期……一个列表。其次，在您开始的递归调用中，s[i:i+1]但根据您的示例，您需要所有前缀，因此s[:i]更合适。另外，在递归调用中你永远不会减少k这是自然的递归步骤。最后，你的停止条件似乎也是错误的。如上所述，如果自然步骤减少，k则自然停止。这是因为将字符串拆分为 1 个部分的唯一方法是字符串本身......if k == 1return [[s]]重要的是要牢记您的最终输出格式，并思考它如何在您的步骤中发挥作用。在这种情况下，您希望以列表的形式返回所有可能排列的列表。因此，在 的情况下k == 1，您只需返回单个字符串列表的列表。现在，作为这一步，您希望每次都采用不同的前缀，并向其添加调用字符串其余部分的所有排列k-1。总而言之，代码可以是这样的：def splt(s, k):&nbsp; &nbsp; if k == 1:&nbsp; # base sace - stop condition&nbsp; &nbsp; &nbsp; &nbsp; return [[s]]&nbsp; &nbsp; res = []&nbsp; &nbsp; # loop over all prefixes&nbsp; &nbsp; for i in range(1, len(s)-k+2):&nbsp; &nbsp; &nbsp; &nbsp; for tmp in splt(s[i:], k-1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # add to prefix all permutations of k-1 parts of the rest of s&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res.append([s[:i]] + tmp)&nbsp; &nbsp; return res您可以在一些输入上对其进行测试，看看它是如何工作的。如果您不限于递归，另一种方法是使用itertools.combinations. 您可以使用它在字符串中创建所有索引组合，将其拆分为多个k部分，然后简单地连接这些部分并将它们放入列表中。原始版本类似于：from itertools import combinationsdef splt(s, k):&nbsp; &nbsp; res = []&nbsp; &nbsp; for indexes in combinations(range(1, len(s)), k-1):&nbsp; &nbsp; &nbsp; &nbsp; indexes = [0] + list(indexes) + [len(s)] # add the edges to k-1 indexes to create k parts&nbsp; &nbsp; &nbsp; &nbsp; res.append([s[start:end] for start, end in zip(indexes[:-1], indexes[1:])]) # concatenate the k parts&nbsp; &nbsp; return res

Answer 2

您实现中的主要问题是您的循环没有执行预期的操作，因为它返回第一个结果而不是附加结果。下面是一个实现示例：def sliding(s, k):&nbsp; &nbsp; # If there is not enough values of k is below 0&nbsp; &nbsp; # there is no combination possible&nbsp; &nbsp; if len(s) < k or k < 1:&nbsp; &nbsp; &nbsp; &nbsp; return []&nbsp; &nbsp; # If k is one, we return a list containing all the combinations,&nbsp; &nbsp; # which is a single list containing the string&nbsp; &nbsp; if k == 1:&nbsp; &nbsp; &nbsp; &nbsp; return [[s]]&nbsp; &nbsp; results = []&nbsp; &nbsp; # Iterate through all the possible values for the first value&nbsp; &nbsp; for i in range(1, len(s) - k + 2):&nbsp; &nbsp; &nbsp; &nbsp; first_value = s[:i]&nbsp; &nbsp; &nbsp; &nbsp; # Append the result of the sub call to the first values&nbsp; &nbsp; &nbsp; &nbsp; for sub_result in sliding(s[i:], k - 1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; results.append([first_value] + sub_result)&nbsp; &nbsp; return resultsprint(sliding("iamfoobar", 4))