string - 文字列のすべてのカバーサブ文字列を生成する

Question

どのように次のようにしますか：文字列を指定して、その文字列をサブ文字列に解析するためのすべての可能な方法を生成します（時間は重要です、スペースは気にしないでください）。たとえば、文字列ABCDが与えられた場合、次を生成する必要があります。

ABCD

A BCD

A BC D

A B CD

AB CD

AB C D

ABC D

A B C D

おそらく再帰的な解決策ですが、私はそれを完全に機能させることができません。

Answer 1

再帰のないPythonの別のソリューション：

def substrings(s):
    for k in xrange(1, len(s)+1):
        for i in xrange(len(s)-k+1):
            yield s[i:i+k]

となることによって

>>> print list(substrings("ABCD"))
['A', 'B', 'C', 'D', 'AB', 'BC', 'CD', 'ABC', 'BCD', 'ABCD']

Answer 2

Python：

def splitstring(s):
  result = [s]
  for i in range(1, len(s)):
    result.extend('%s %s' % (s[:i], x) for x in splitstring(s[i:]))
  return result

Answer 3

特定の分割を取得するには：

• まず、分割するインデックスを決定します。
• 次に、指定されたインデックスで文字列を分割します。

長さの文字列の場合、n分割インデックスの特定のセットはのの要素powersetです{1, ..., n}。

Pythonの場合：

from itertools import combinations, chain

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def pairs(seq, end):
    "pairs([13,23,33], 55) --> (0,13) (13,23) (23,33) (33,55)"
    return zip(chain((0,), seq), chain(seq, (end,)))

def allsplits(s):
    "allsplits('abc') --> ['abc'] ['a', 'bc'] ['ab', 'c'] ['a', 'b', 'c']"
    for split_indices in powerset(range(1,len(s))):
        yield [s[i:j] for i,j in pairs(split_indices, len(s))]

print(list( allsplits('abcd') ))
# [['abcd'], ['a', 'bcd'], ['ab', 'cd'], ['abc', 'd'], ['a', 'b', 'cd'], ['a', 'bc', 'd'], ['ab', 'c', 'd'], ['a', 'b', 'c', 'd']]