2

辞書順でソートされた、アルファベットと最大文字列長を指定して、すべての可変長文字列のイテレータ/ジェネレータを作成しようとしています。

現在、ネストされた itertools product() を使用する単純なメソッドがあり、ソートに進みます。これは max_len_string が小さい場合にはうまく機能しますが、私の目標の使用法 (max_len_string=32 前後) では、実用的であるにはあまりにも多くの一時ストレージを使用します。

並べ替えでシーケンス全体を丸呑みする代わりに、このアルゴリズムが反復ごとに少量の定数スペースのみを使用するようにする方法はありますか?

from itertools import product
def variable_strings_complete(max_len_string, alphabet=range(2)):
    yield from sorted(string
                      for i in range(1, max_len_string+1)
                      for string in product(alphabet, repeat=i))

list(variable_strings_complete(3))

[(0,),
 (0, 0),
 (0, 0, 0),
 (0, 0, 1),
 (0, 1),
 (0, 1, 0),
 (0, 1, 1),
 (1,),
 (1, 0),
 (1, 0, 0),
 (1, 0, 1),
 (1, 1),
 (1, 1, 0),
 (1, 1, 1)]
4

2 に答える 2

0

これはうまくいくようです（編集 - ジェネレーターに修正しました）：

from itertools import chain

def variable_strings_complete(max_len, alphabet=range(2)):
    alphabet = sorted(map(str, alphabet))

    def complete_partial(partial, alph_idx):
        to_returns = (partial + a for a in alphabet)

        if alph_idx == (max_len - 1):
            yield from to_returns
        else:
            for r in to_returns:
                n = complete_partial(r, alph_idx + 1)
                yield from chain([r], n)

    yield from complete_partial("", 0)

print(list(variable_strings_complete(3)))

戻り値：

['0', '00', '000', '001', '01', '010', '011', '1', '10', '100', '101', '11', '110', '111']

そして、それは他のアルファベットでも機能します:

print(list(variable_strings_complete(3, "ab")))

収量

['a', 'aa', 'aaa', 'aab', 'ab', 'aba', 'abb', 'b', 'ba', 'baa', 'bab', 'bb', 'bba', 'bbb']
于 2015-03-18T05:40:44.207 に答える