我试图编写一个Python函数(至少最初是这样)来生成长度为k(其中k>;0)的所有子序列。由于我只需要唯一的子序列,所以我将子序列和部分子序列都存储在set
s中。它看起来…太复杂了…我应该可以滥用itertools
或递归来做我想做的事情。有人能做得更好吗?在
from typing import Set, Tuple
def subsequences(string: str, k: int) -> Set[Tuple[str, ...]]:
if len(string) < k:
return set()
start = tuple(string[:k])
result = {start}
prev_state = [start]
curr_state = set()
for s in string[k:]:
for p in prev_state:
for i in range(k):
new = p[:i] + p[i + 1 :] + (s,)
curr_state.add(new)
result.update(curr_state)
prev_state = list(curr_state)
curr_state.clear()
return result
(对于上下文,我对k-strictly piecewise languages的归纳感兴趣,这是正规语言的一个可有效学习的子类,语法可以用所有合法的k-子序列来描述。在
<>最后,我也在考虑C++中的这一点,其中{{CD3}}不如Python ^ {< CD4>}那么强大。
您需要一组来自
n
项的r
组合(不带替换,<= (n choose r)
)。在编码
选项1
^{pr2}$选项2
两个选项产生相同(无序)的输出。但是:
通过
> pip install more_itertools
安装more_itertools
。在另请参见Python编写的
itertools.combinations
的rough implementation。在相关问题 更多 >
编程相关推荐