Получить все возможные разделы str любой длины

Question

Я хочу найти все возможные разделы строки без пустых строк и должен содержать всегда символ (не должен содержать исходную строку)

Например:

s = '1234'

partitions(s)  # -> [['1', '2', '3', '4'], ['1', '2', '34'], ['1', '23', '4']
               #     ['12', '3', '4'], ['12', '34'], ['1', '234'], ['123', '4']]
               # should not contain ['1234']

РЕДАКТИРОВАТЬ: Может быть в любом порядке

Почему мой вопрос не является дубликатом:

Я не хочу перестановок:

from itertools import permutations

s = '1234'
permutations(s) # returns ['1', '2', '3', '4'], ['1', '2', '4', '3']...

Но я хочу, чтобы строка была разбита на несколько частей (пожалуйста, посмотрите на первый код)

Спасибо!

Answer 1

Вы можете определить рекурсивную (генераторную) функцию. Идея такова: объединить префиксы строки всей длины со всеми разделами оставшейся строки.

def partitions(s):
    if len(s) > 0:
        for i in range(1, len(s)+1):
            first, rest = s[:i], s[i:]
            for p in partitions(rest):
                yield [first] + p
    else:
        yield []

Результаты для partitions("1234"):

['1', '2', '3', '4']
['1', '2', '34']
['1', '23', '4']
['1', '234']
['12', '3', '4']
['12', '34']
['123', '4']
['1234']

Обратите внимание, что содержит , содержит ['1234'], но впоследствии его легко отфильтровать, например, как print([p for p in partitions("1234") if len(p) > 1]), или вы можете собрать результаты в list и затем pop в последнем элементе. Добавление этого непосредственно к рекурсивной функции было бы более сложным, поскольку каждый, кроме вызова верхнего уровня должен возвращать этот "полный" раздел.

Answer 2

Идея может быть в следующем. Получив строку «1234», вы разбиваете строку, вычисляя позиции подстрок.

import itertools

s="1234"

possibilities = []

for i in range(1,len(s)):

    comb = itertools.combinations(range(1,len(s)), i)

    possibilities+= [[s[0:c[0]]] + [s[c[i]:c[i+1]] for i in range(len(c)-1)] + [s[c[-1]:]] for c in comb]

выход

#[['1', '234'], ['12', '34'], ['123', '4'], ['1', '2', '34'], ['1', '23', '4'], ['12', '3', '4'], ['1', '2', '3', '4']]

Это решение не содержит ['1234'] на выходе (это потому, что основной цикл начинается с 1, а не с 0).

Просто сноска.
Количество способов разбить строку без включения исходной строки:

Идея, на которой основано это решение, заключается в следующем. По генерации каждого из них по формуле выше. Число велико, и алгоритм полиномиального времени не может существовать (по крайней мере, вы должны генерировать каждый элемент выходных данных, поэтому Ω(2^n) является нижней границей для общей задачи).

Answer 3

Используйте код из этого вопроса SO , чтобы вывести список всех подстрок (перенесенных в python 3), затем удалите основную строку. Затем создайте все перестановки и отфильтруйте только разрешенные.

import itertools


def get_all_substrings(input_string):
    length = len(input_string)
    return [input_string[i:j+1] for i in range(length) for j in range(i,length)]


def filter_func(string, iterable):
    """ Leave only permutations that contain all letters from the string and have the same char count. """
    all_chars = ''.join(iterable)
    return True if len(all_chars) == len(string) and all(char in all_chars for char in string) else False


s = '1234'
partitions = get_all_substrings(s)
partitions.remove(s)  # remove '1234' (results should be only substrings not equal to the original string)

results = []
# create all permutations of all substrings, for all sub-lengths of the string length (1, 2, 3...)
for i in range(len(s)):
    permutations = list(itertools.permutations(partitions, i + 1))
    accepted_permutations = tuple(filter(lambda p: filter_func(s, p), permutations))  # filter out unwanted permutations
    results += accepted_permutations

res = list(set(tuple(sorted(l)) for l in results))  # filter out duplicates with different order
print(res)

Это не так хорошо, как рекурсивное решение, описанное выше, но я уже написал его, поэтому разместил его: D Редактировать: полностью переработан вопрос.