c++

I have a string like "0189", for which I need to generate all subsequences, but the ordering of the individual characters must be kept, ie, here 9 should not come before 0, 1 or 8. Ex: 0, 018, 01, 09, 0189, 18, 19, 019, etc.

Another example is "10292" for which subsequences would be: 1, 10, 02, 02, 09, 29, 92, etc. As you might have noticed '02' two times, since '2' comes twice in the given string. But again things like: 21, 01, 91 are invalid as order is to be maintained.

Any algorithm or psuedo code, which could be implemented in C/C++ would be appreciated!

---

I'd recommend using the natural correspondence between the power set of a sequence and the set of binary numbers from 0 to 2^n - 1 , where n is the length of the sequence.

In your case, n is 4, so consider 0 = 0000 .. 15 = 1111 ; where there is a 1 in the binary expression include the corresponding item from the sequence. To implement this you'll need bitshift and binary operations:

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);
}

Also consider how you'd handle sequences longer than can be covered by an int (hint: consider overflow and arithmetic carry).

---

Try a recursive approach:

the set of subsequences can be split into the ones containing the first character and the ones not containing it

the ones containing the first character are build by appending that character to the subsequences which don't contain it (+ the subsequence which contains only the first character itself)

---

在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/61502.html

上一篇: 将树转换为反转树？

下一篇: C ++