生成子序列

Question

我有一个像"0189"这样的字符串,我需要生成所有子序列,但必须保留各个字符的顺序,即这里9不应该出现在0,1或8之前.例如:0,018,01 ,09,0189,18,19,019等

另一个例子是"10292",子序列将是:1,10,202,02,09,29,92等.你可能已经注意到'02'两次,因为'2'在给定的字符串中出现两次.但是,21,11,91之类的东西也是无效的,因为要维持秩序.

任何算法或伪代码,可以用C/C++实现,将不胜感激!

Answer 1

尝试递归方法:

• 子序列集可以分为包含第一个字符的子集和不包含第一个字符的子序列
• 包含第一个字符的那些是通过将该字符附加到不包含它的子序列(+仅包含第一个字符本身的子序列)来构建的.

Answer 2

我建议使用之间的天然对应功率设定的序列,并从该组二进制数的0到2^n - 1,在这里n是序列的长度.

在你的情况下,n是4,所以考虑0 = 0000.. 15 = 1111; 其中1,二进制表达式中有a 包含序列中的相应项.要实现这一点,您需要bitshift和二进制操作:

for (int i = 0; i < (1 << n); ++i) {
    std::string item;
    for (j = 0; j < n; ++j) {
        if (i & (1 << j)) {
            item += sequence[j];
        }
    }
    result.push_back(item);
}

还要考虑如何处理序列的时间长于(可以int考虑溢出和算术进位).