Я видел много вопросов о получении всех возможных подстрок (т.е. Смежных наборов символов), но ни один из них не генерировал все возможные строки, включая комбинации его подстрок.
Например, пусть:
x = 'abc'
Я хотел бы, чтобы результат был чем-то вроде:
['abc', 'ab', 'ac', 'bc', 'a', 'b', 'c']
Главное, что мы можем удалить несколько символов, которые не смежны в исходной строке (а также смежные).
Вот что я пробовал до сих пор:
def return_substrings(input_string):
length = len(input_string)
return [input_string[i:j + 1] for i in range(length) for j in range(i, length)]
print(return_substrings('abc'))
Однако это только удаляет наборы смежных строк из исходной строки и не возвращает элемент 'ac' из приведенного выше примера.
Другой пример: если мы используем строку 'abcde', выходной список должен содержать элементы 'ace', 'bd' и т.д.
Вы можете сделать это легко, используя itertools.combinations
>>> from itertools import combinations
>>> x = 'abc'
>>> [''.join(l) for i in range(len(x)) for l in combinations(x, i+1)]
['a', 'b', 'c', 'ab', 'ac', 'bc', 'abc']
Если вы хотите, чтобы это было в обратном порядке, вы можете заставить функцию range возвращать свою последовательность в обратном порядке.
>>> [''.join(l) for i in range(len(x),0,-1) for l in combinations(x, i)]
['abc', 'ab', 'ac', 'bc', 'a', 'b', 'c']
Это забавное упражнение. Я думаю, что другие ответы могут использовать itertools.product или itertools.combinations. Но просто для удовольствия, вы также можете сделать это рекурсивно с чем-то вроде
def subs(string, ret=['']):
if len(string) == 0:
return ret
head, tail = string[0], string[1:]
ret = ret + list(map(lambda x: x+head, ret))
return subs(tail, ret)
subs('abc')
# returns ['', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
@Sunitha ответ предоставил правильный инструмент для использования. Я просто пойду и предложу улучшенный способ при использовании вашего метода return_substrings. По сути, мое решение позаботится о дубликатах.
Я буду использовать "ABCA" для подтверждения правильности моего решения. Обратите внимание, что он будет содержать дубликат 'A' в возвращенном списке принятых ответов.
Python 3. 7+ решение,
x= "ABCA"
def return_substrings(x):
all_combnations = [''.join(l) for i in range(len(x)) for l in combinations(x, i+1)]
return list(reversed(list(dict.fromkeys(all_combnations))))
# return list(dict.fromkeys(all_combnations)) for none-reversed ordering
print(return_substrings(x))
>>>>['ABCA', 'BCA', 'ACA', 'ABA', 'ABC', 'CA', 'BA', 'BC', 'AA', 'AC', 'AB', 'C', 'B', 'A']
Решение Python 2.7,
Вам придется использовать OrderedDict вместо обычного dict. Следовательно,
return list(reversed(list(dict.fromkeys(all_combnations))))
становится
return list(reversed(list(OrderedDict.fromkeys(all_combnations))))
Заказ не имеет значения для вас?
Вы можете уменьшить сложность кода, если порядок не актуален,
x= "ABCA"
def return_substrings(x):
all_combnations = [''.join(l) for i in range(len(x)) for l in combinations(x, i+1)]
return list(set(all_combnations))
def return_substrings(s):
all_sub = set()
recent = {s}
while recent:
tmp = set()
for word in recent:
for i in range(len(word)):
tmp.add(word[:i] + word[i + 1:])
all_sub.update(recent)
recent = tmp
return all_sub