Python рекурсия для разделения строки скользящим окном

Question

Недавно я столкнулся с интересной задачей кодирования, которая включает в себя разделение строки на несколько перестановок с заданным размером K-limit.

Например:

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

Ваша первая основная проблема заключается в том, что, хотя вы используете al oop, вы сразу же возвращаете единственный список. Итак, сколько бы вы ни исправляли все вокруг, ваш результат никогда не будет соответствовать тому, что вы ожидаете, поскольку он будет ... единым списком.

Во-вторых, при рекурсивном вызове вы начинаете с s[i:i+1], но в соответствии с в вашем примере вам нужны все префиксы, поэтому что-то вроде s[:i] более подходит.

Дополнительно, в рекурсивном вызове вы никогда не уменьшаете k, который является естественным рекурсивным шагом.

Наконец , ваше условие остановки также кажется неправильным. Как и выше, если естественным шагом является уменьшение k, естественная остановка будет if k == 1, затем return [[s]]. Это потому, что единственный способ разбить строку на 1 часть - это сама строка ...

---

Важно помнить о своем окончательном формате вывода и думать, как это может работать на вашем этапе . В этом случае вы хотите вернуть список всех возможных перестановок в виде списков. Таким образом, в случае 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

Основная проблема в вашей реализации заключается в том, что ваш l oop не выполняет то, что должен делать, поскольку он возвращает первый результат вместо добавления результатов.

Вот пример реализации:

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))