按字母顺序生成给定字符串的所有子字符串（按字典顺序）

Question

我最近看到了这个问题，并且真的在实施它。

问题是从给定的字符串生成所有可能的按字母顺序排列的子字符串。

更小的例子：对于字符串xcv

我需要生成输出：

c cv cvx v vx x

更大的例子：对于字符串hgrte

我需要生成以下子字符串：

e
eg
egh
eghr
eghrt
eght
egr
egrt
egt
eh
ehr
ehrt
eht
er
ert
et
g
gh
ghr
ghrt
ght
gr
grt
gt
h
hr
hrt
ht
r
rt
t

这是我的实现，没有产生所需的输出。

s = sorted(list(input()))
s = ''.join(s)
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        temp = s[i:j]
        print(''.join(temp))

这是我的代码的输出：

e
eg
egh
eghr
eghrt
g
gh
ghr
ghrt
h
hr
hrt
r
rt
t
[]

我知道我必须在打印后使用回溯和递归eghrt，但我真的很难实现它。提前致谢:)

Answer 1

你忘了考虑不连续的子串。一个简单的方法是使用 itertools。

import itertools

word = sorted(list(input()))
print(sorted(set([''.join(j) for i in range(len(word)) for j in itertools.combinations(word, i)])))

这样就可以了。如果您不想使用标准库，可以使用位掩码来获取所有可能的子字符串。

Answer 2

您可以遍历不同的长度并使用 itertools.combinations 生成字母组合：

from itertools import combinations
s = sorted(input())
print(*sorted(''.join(c) for i in range(len(s)) for c in combinations(s, i + 1)), sep='\n')

Answer 3

如果递归不是一个明确的要求，你可以不用递归来做：

from itertools import chain, combinations

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

for w in (''.join(sorted(x)) for x in powerset(s) ):
    print(w)

取自How to get all subsets of a set? (powerset)

的powerset函数

Answer 4

s = 'abc'
n = len(s)
p = 2 ** n   # total number of power sets 
res = []
for i in range(1, p):
    tmp = ''
    for j in range(n):
        if i & (1 << j):
            tmp += s[j]
    res.append(tmp)

print(sorted(res))   # ['a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']


# Time Complexity: O(2^n * n)
# Space Complexity: O(n)

按字母顺序生成给定字符串的所有子字符串（按字典顺序）

Generate all substrings(in lexicographic order)of given string in alphabetical order

python

string

recursion

backtracking