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

Question

最近，我遇到了一个有趣的编码任务，涉及将字符串拆分为具有给定 K 限制大小的多个排列。例如：s = "iamfoobar"k = 4  # the max number of the items on a list after the splits可以拆分为以下组合[    ["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):

    if k == 1:  # base sace - stop condition

        return [[s]]

    res = []

    # loop over all prefixes

    for i in range(1, len(s)-k+2):

        for tmp in splt(s[i:], k-1):

            # add to prefix all permutations of k-1 parts of the rest of s

            res.append([s[:i]] + tmp)

    return res

您可以在一些输入上对其进行测试，看看它是如何工作的。

如果您不限于递归，另一种方法是使用itertools.combinations. 您可以使用它在字符串中创建所有索引组合，将其拆分为多个k部分，然后简单地连接这些部分并将它们放入列表中。原始版本类似于：

from itertools import combinations

def splt(s, k):

    res = []

    for indexes in combinations(range(1, len(s)), k-1):

        indexes = [0] + list(indexes) + [len(s)] # add the edges to k-1 indexes to create k parts

        res.append([s[start:end] for start, end in zip(indexes[:-1], indexes[1:])]) # concatenate the k parts

    return res

Answer 2

您实现中的主要问题是您的循环没有执行预期的操作，因为它返回第一个结果而不是附加结果。

下面是一个实现示例：

def sliding(s, k):

    # If there is not enough values of k is below 0

    # there is no combination possible

    if len(s) < k or k < 1:

        return []

    # If k is one, we return a list containing all the combinations,

    # which is a single list containing the string

    if k == 1:

        return [[s]]

    results = []

    # Iterate through all the possible values for the first value

    for i in range(1, len(s) - k + 2):

        first_value = s[:i]

        # Append the result of the sub call to the first values

        for sub_result in sliding(s[i:], k - 1):

            results.append([first_value] + sub_result)

    return results

print(sliding("iamfoobar", 4))