整天都在经历这个，不知道在这里做什么，我觉得我需要在这里使用递归函数，任何技巧都会很棒(要采取的步骤，算法等(
给定一个单词 w，w 的良好子序列定义为单词 w' 使得
w' 中的所有字母都不同;
w' 是通过删除 w 中的一些字母从 w 获得的。
按字典顺序返回所有良好子序列的列表，不带重复项
预期成果：
def good_subsequences(word):
'''
>>> good_subsequences('')
['']
>>> good_subsequences('aaa')
['', 'a']
>>> good_subsequences('aaabbb')
['', 'a', 'ab', 'b']
>>> good_subsequences('aaabbc')
['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']
>>> good_subsequences('aaabbaaa')
['', 'a', 'ab', 'b', 'ba']
>>> good_subsequences('abbbcaaabccc')
['', 'a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb']
>>> good_subsequences('abbbcaaabcccaaa')
['', 'a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac','bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']
>>> good_subsequences('abbbcaaabcccaaabbbbbccab')
['', 'a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac','bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']
'''
我在想的是
def good_subsequences(word):
L = ['']
current_char = ''
for i in range(0,len(word)):
if current_char != word[i]:
L.append(word[i])
current_char = word[i]
L = ''.join(L)
#call up _good_sub(L)
def _good_sub(word):
#do a recursive function
递归生成器方法，与一些蛮力解决方案相比，具有后续排序和很少的过度生产：
from itertools import groupby
def simple(word, without=''):
# remove adjacent duplicates and anything in 'without'
return ''.join(k for k, _ in groupby(word) if k not in without)
def _gs(word):
seen = set()
s_word = simple(word)
yield ''
for i, char in enumerate(s_word):
for sub in _gs(simple(s_word[i+1:], char)):
new_sub = char + sub
if new_sub not in seen:
seen.add(new_sub)
yield new_sub
def good_subsequences(word):
return sorted(_gs(word))
>>> good_subsequences('')
['']
>>> good_subsequences('aaa')
['', 'a']
>>> good_subsequences('aaabbb')
['', 'a', 'ab', 'b']
>>> good_subsequences('aaabbc')
['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']
>>> good_subsequences('aaabbaaa')
['', 'a', 'ab', 'b', 'ba']
>>> good_subsequences('abbbcaaabccc')
['', 'a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb']
你可以开始做这样的事情：
def good_subsequences(word):
Letter_order = [word[0]]
substrings = ['']
for i in range(1,len(word)):
if Letter_order[-1] != word[i]:
Letter_order .append(word[i])
现在，在 for 循环之后，您拥有包含需要包含在最终子字符串数组中的所有字母顺序的数组。在这里，您可以使用辅助函数根据字母在Letter_order数组中的顺序顺序检查所有可能的字母组合。
这只提取连续的子序列
我相信这是一个简单的贪婪搜索：
def good_subsequences(w):
L = {''}
j = 0
for i in range(len(w)):
for k in range(i, j):
L.add(w[i:j])
while j < len(w) and w[j] not in w[i:j]:
j += 1
L.add(w[i:j])
return L
在你的例子中，有一件事我不明白。为什么'abbbcaaabccc'会产生'bac'？
这只是蛮力。 当你的字母表中有很多不同的字符时，不要尝试这个......但是，如果您有很多角色重复，它可能会表现良好。
from itertools import combinations, permutations
def in_word(strg, word):
i = 0
for char in strg:
try:
i = word.index(char, i)
except ValueError:
return False
return True
def good_subsequences(word):
ret = ['']
alphabet = set(word)
for r in range(len(alphabet)):
for comb in combinations(alphabet, r+1):
for perm in permutations(comb, r+1):
strg = ''.join(perm)
if in_word(strg, word):
ret.append(strg)
return ret
它使用set减少您对唯一字母的输入，然后循环 1、2、3、...、n 字母组合，然后循环这些组合的排列。 然后in_word检查该排列是否出现在您的原始单词中(按该顺序(。
也许这不是一个"完整"的答案，也没有为你提供代码，但这是针对你的问题的算法方法。
首先以与原始问题等效的方式改写问题。但"更接近"可能的实现。
给定一个单词 w，找到
最长- 的好子序列(不同字母的最长子序列( 一个好的子序列的所有子序列
- 都是好的(但不同长序列的子序列可能重叠：ABC和ACB都有AB作为子序列(
很容易应付第二部分(只需构建子序列并消除重复项(
要获得最长的字母，您需要保留每个字母一次，保留不同的位置。
但首先，请注意重复的字母无关紧要。AAABBBBBBBCCAAA将具有与ABCA相同的输出。所以首先，清除所有连续的配音
现在，您需要将每个字母的所有位置相互组合。 例如，如果字母a在您的单词中出现 3 次，您需要尝试 3 次。如果字母 b 出现两次，则需要尝试两次，依此类推。例：
Abacba最多有3x2x1 = 6个，每个包含一个a，一个b和一个c => abc，acb，bac，acb，bca，cba。
现在删除重复的最长的良好序列，然后继续上面的第二个项目符号点