3

「0189」のような文字列があり、すべてのサブシーケンスを生成する必要がありますが、個々の文字の順序を維持する必要があります。つまり、ここでは9を0、1、または8の前に配置しないでください。例：0、018、01 、09、0189、18、19、019など。

別の例は「10292」で、サブシーケンスは次のようになります。1、10、02、02、09、29、92など。「2」は指定された文字列に2回含まれるため、「02」は2回お気づきかもしれません。ただし、21、01、91のようなものは、順序が維持されるため無効です。

C /C++で実装できる任意のアルゴリズムまたは疑似コードをいただければ幸いです。

4

4 に答える 4

8

再帰的なアプローチを試してください。

  • サブシーケンスのセットは、最初の文字を含むものと含まないものに分割できます
  • 最初の文字を含むものは、その文字を含まないサブシーケンスにその文字を追加することによって構築されます（+最初の文字自体のみを含むサブシーケンス）
于 2012-08-02T09:04:45.620 に答える
6

シーケンスのべき集合0とからまでの2進数のセットの間の自然な対応を使用することをお勧めします。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また、 （ヒント：オーバーフローと算術キャリーを考慮してください）でカバーできるよりも長いシーケンスを処理する方法を検討してください。

于 2012-08-02T09:02:26.893 に答える
1

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]:
于 2012-08-04T08:24:06.700 に答える
0 
__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']
于 2012-08-02T13:42:31.400 に答える