生成子序列
我有一个像“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 ++实现，将不胜感激！
我建议使用序列的幂集和从0到2^n - 1的二进制数集之间的自然对应关系，其中n是序列的长度。
在你的情况下， n是4，所以考虑0 = 0000 .. 15 = 1111 ; 其中二进制表达式中有1包含序列中的相应项。 要实现这一点，你需要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所涵盖的更长的序列（提示：考虑溢出和算术进位）。
尝试递归方法：
- 子序列集可以分为包含第一个字符的子集和不包含第一个字符的子序列
- 包含第一个字符的那些是通过将该字符附加到不包含它的子序列（+仅包含第一个字符本身的子序列）来构建的。
在Python中：
In [29]: def subseq(s): return ' '.join((' '.join(''.join(x) for x in combs(s,n)) for n in range(1, len(s)+1))) In [30]: subseq("0189") Out[30]: '0 1 8 9 01 08 09 18 19 89 018 019 089 189 0189' In [31]: subseq("10292") Out[31]: '1 0 2 9 2 10 12 19 12 02 09 02 29 22 92 102 109 102 129 122 192 029 022 092 292 1029 1022 1092 1292 0292 10292' In [32]:
__author__ = 'Robert' from itertools import combinations g = combinations(range(4), r=2) print(list(g)) #[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] def solve(string_): n = len(string_) for repeat in range(1, len(string_) + 1): combos = combinations(range(len(string_)), r=repeat) for combo in combos: sub_string = "".join(string_[i] for i in combo) yield sub_string print(list(solve('0189'))) #['0', '1', '8', '9', '01', '08', '09', '18', '19', '89', '018', '019', '089', '189'] #using recursion def solve2(string_, i): if i >= len(string_): return [""] #no sub_strings beyond length of string_ character_i = string_[i] all_sub_strings = solve2(string_, i + 1) all_sub_strings += [character_i + sub_string for sub_string in all_sub_strings] return all_sub_strings print(solve2('0189', 0)) #['', '9', '8', '89', '1', '19', '18', '189', '0', '09', '08', '089', '01', '019', '018', '0189']