C ++

我有一个类似“0189”的字符串，为此我需要生成所有的子序列，但是必须保留单个字符的顺序，即这里9不应该在0,1或8之前出现。例如：0,018,01 ，09,0189,18,19,019等。

另一个例子是“10292”，其中的子序列是：1,10,02,02,09,29,92等。由于'2'在给定字符串中出现了两次，因此您可能已经注意到'02'两次了。 但是，像21：01,91那样的事情是无效的，因为要维持秩序。

任何算法或伪代码，可以在C / C ++中实现，将不胜感激！

---

我建议使用序列的幂集与从0到2^n - 1的二进制数集之间的自然对应关系，其中n是序列的长度。

在你的情况下， n是4，所以考虑0 = 0000 .. 15 = 1111 ; 在二进制表达式中有一个1包含序列中的相应项目。 要实现这一点，您需要位移和二进制操作：

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]: 

链接地址: http://www.djcxy.com/p/61501.html

上一篇: c++

下一篇: Implementing a simple Trie for efficient Levenshtein Distance calculation