通过位运算快速生成所有的子序列

约 664 字大约 2 分钟

2026-01-09

一、子序列的本质

子序列是从原字符串中选择任意数量的字符（可以是 0 个、1 个、...、所有字符），且保持这些字符的原始顺序形成的字符串。

例如：原字符串 "abc" 的子序列包括 "a", "b", "c", "ab", "ac", "bc", "abc" 和空字符串 ""（共 $2^3 = 8$ 种可能性）。

二、位掩码（Bitmask）的引入

假设字符串长度为 n，我们可以用一个 n 位的二进制数来表示是否选择某个字符：

二进制数的每一位对应原字符串的一个字符。
如果某一位是 1，表示选择对应的字符；如果是 0，表示不选择。

例如，对于字符串 "abc"（n=3）：

二进制数	十进制	选择情况	生成子序列
`101`	5	选择第 1 个字符 "a" 和第 3 个字符 "c"	`"ac"`
`010`	2	选择第 2 个字符 "b"	`"b"`

三、遍历所有可能的二进制数

所有可能的二进制数范围是 0（全 0）到 $2^n - 1$ （全 1）。例如，n=3 时：

范围是 000 (0) 到 111 (7)，共 $2^3 = 8$ 种可能。
每个二进制数对应一种子序列选择方式。
如果包含 000 (0)，对应空字符串 ""。若不需要空字符串，可以从 1 开始遍历。

四、如何将二进制数转换为子序列？

1. 外层循环：遍历所有可能的二进制数

对于 n=3，遍历 1 (001) 到 7 (111)。

2. 内层循环：检查每一位是否为 1

对于每个二进制数 mask，遍历其每一位 i（从 0 到 n-1）。
如果 mask 的第 i 位是 1（即 mask & (1 << i) 为真），则将原字符串的第 i 个字符加入子序列。

五、代码示例

def get_all_subsequences(s):
    n = len(s)
    subsequences = []
    # 遍历 1 到 2^n - 1 (排除空字符串)
    for mask in range(1, 1 << n):
        subseq = []
        for i in range(n):
            # 检查 mask 的第 i 位是否为 1
            if mask & (1 << i):
                subseq.append(s[i])
        subsequences.append(''.join(subseq))
    return subsequences

# 测试
print(get_all_subsequences("abc"))
# 输出: ['a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']

六、应用场景

在处理类似 X 质数 的问题时，我们需要检查一个数字的所有数字子序列。通过这种位运算的方式，可以非常高效地生成所有组合并进行判断。

def solve_x_prime(num):
    s = str(num)
    n = len(s)
    for mask in range(1, 1 << n):
        subseq_str = ""
        for i in range(n):
            if mask & (1 << i):
                subseq_str += s[i]
        
        # 将生成的子序列转换为整数并判断是否为质数
        p = int(subseq_str)
        if is_prime(p):
            return True
    return False