如何修改Python代码以获取包含非相邻子串的所有子串？

给定字符串示例'abc'，需要输出的所有子串包括：'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc'，其中'ac'属于非相邻子串。现有一段Python代码仅能生成所有相邻子串：

lines = input()
res = [lines[i: j] for i in range(len(lines)) for j in range(i + 1, len(lines) + 1)]

修改方案 #

原来的代码通过连续切片生成相邻子串，要覆盖非相邻子串，本质是生成原字符串的所有非空字符子集（保持字符原顺序），以下是两种实现方式：

方法1：使用itertools.combinations

借助itertools.combinations生成所有位置的非空组合，再按原顺序拼接字符：

import itertools

lines = input()
res = []
# 遍历子串的所有可能长度（1到字符串总长度）
for sub_len in range(1, len(lines) + 1):
    # 生成所有长度为sub_len的位置组合
    for indices in itertools.combinations(range(len(lines)), sub_len):
        # 根据位置拼接对应字符
        res.append(''.join(lines[i] for i in indices))

方法2：二进制枚举法（无需额外库）

用二进制数的每一位标记字符是否被选中，遍历所有非空组合：

lines = input()
str_len = len(lines)
res = []
# 遍历1到2^str_len -1的所有数，对应所有非空子集
for mask in range(1, 1 << str_len):
    substr = ''
    for i in range(str_len):
        # 检查第i位是否为1，是则加入对应字符
        if mask & (1 << i):
            substr += lines[i]
    res.append(substr)

两种方法最终都能生成包含非相邻子串的所有目标结果。

内容的提问来源于stack exchange，提问作者ryrie23