在给定字符串中查找所有可能的子序列

Question

我写了这段代码，它打印给定字符串的所有子字符串，但我希望它打印所有可能的子序列。

from itertools import combinations_with_replacement
s = 'MISSISSIPPI'
lst = []
for i,j in combinations_with_replacement(range(len(s)), 2):
        print(s[i:(j+1)])

Answer 1

一个简单的方法是验证您正在制作的列表是否已经包含您正在迭代的情况。如果您已经看到它，则跳过它，如果没有，则将其附加到您看到的组合列表中。

from itertools import combinations_with_replacement

s = 'MISSISSIPPI'
lst = []

for i,j in combinations_with_replacement(range(len(s)), 2):
    if s[i:(j+1)] not in lst:
        lst.append(s[i:(j+1)]) # save new combination into list
        print(lst[-1]) # print new combination

为确保涵盖所有情况，绘制循环将遍历的组合图确实很有帮助。假设一个通用字符串，其中字母由它们在 python 列表中的位置表示，例如 0 到 3.

这是"combinations_with_replacement"

生成的数字

00, 01, 02, 03,
11、12、13，
22、23、
33

Answer 2

使用combinations获取子序列。这就是 combinations 的目的。

from itertools import combinations

def all_subsequences(s):
    out = set()
    for r in range(1, len(s) + 1):
        for c in combinations(s, r):
            out.add(''.join(c))
    return sorted(out)

示例：

>>> all_subsequences('HELLO')
['E', 'EL', 'ELL', 'ELLO', 'ELO', 'EO', 'H', 'HE', 'HEL', 'HELL', 'HELLO', 'HELO',
 'HEO', 'HL', 'HLL', 'HLLO', 'HLO', 'HO', 'L', 'LL', 'LLO', 'LO', 'O']
>>> all_subsequences('WORLD')
['D', 'L', 'LD', 'O', 'OD', 'OL', 'OLD', 'OR', 'ORD', 'ORL', 'ORLD', 'R', 'RD',
 'RL', 'RLD', 'W', 'WD', 'WL', 'WLD', 'WO', 'WOD', 'WOL', 'WOLD', 'WOR', 'WORD',
 'WORL', 'WORLD', 'WR', 'WRD', 'WRL', 'WRLD']

在给定字符串中查找所有可能的子序列

finding all possible subsequences in a given string

python

combinations

subsequence