生成所有唯一的kssubsequence

Question

我试图编写一个Python函数（至少最初是这样）来生成长度为k（其中k>；0）的所有子序列。由于我只需要唯一的子序列，所以我将子序列和部分子序列都存储在sets中。它看起来…太复杂了…我应该可以滥用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>}那么强大。

Answer 1

您需要一组来自n项的r组合（不带替换，<= (n choose r)）。在

import itertools as it

import more_itertools as mit

编码

选项1

^{pr2}$

选项2

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

两个选项产生相同（无序）的输出。但是：

• 选项1采用所有组合的集合（包括重复项）
• 选项2不计算重复的中间产物

通过> pip install more_itertools安装more_itertools。在

另请参见Python编写的itertools.combinations的rough implementation。在