我试图编写一个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严格的分段语言的归纳感兴趣,这是常规语言的有效学习的子类,并且语法可以由所有合法的k子序列表征。
最终,我还考虑在C ++中做到这一点,而C ++的std::make_tuple
功能却不如Python强大tuple
。)
您需要一组项目r
组合n
(不包括替换项,<= (n choose r)
。
给定
import itertools as it
import more_itertools as mit
码
set(it.combinations("foo", 2))
# {('f', 'o'), ('o', 'o')}
set(it.combinations("foobar", 3))
# {('b', 'a', 'r'),
# ('f', 'a', 'r'),
# ('f', 'b', 'a'),
# ('f', 'b', 'r'),
# ('f', 'o', 'a'),
# ('f', 'o', 'b'),
# ('f', 'o', 'o'),
# ('f', 'o', 'r'),
# ('o', 'a', 'r'),
# ('o', 'b', 'a'),
# ('o', 'b', 'r'),
# ('o', 'o', 'a'),
# ('o', 'o', 'b'),
# ('o', 'o', 'r')}
选项2 -more_itertools.distinct_combinations
list(mit.distinct_combinations("foo", 2))
# [('f', 'o'), ('o', 'o')]
list(mit.distinct_combinations("foobar", 3))
# [('f', 'o', 'o'),
# ('f', 'o', 'b'),
# ('f', 'o', 'a'),
# ('f', 'o', 'r'),
# ('f', 'b', 'a'),
# ('f', 'b', 'r'),
# ('f', 'a', 'r'),
# ('o', 'o', 'b'),
# ('o', 'o', 'a'),
# ('o', 'o', 'r'),
# ('o', 'b', 'a'),
# ('o', 'b', 'r'),
# ('o', 'a', 'r'),
# ('b', 'a', 'r')]
这两个选项产生相同(无序)的输出。然而:
more_itertools
通过安装> pip install more_itertools
。
也看到了粗糙实现的itertools.combinations
书面Python的。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句