2

CHAR_LISTの範囲内で、動的文字セットのすべての組み合わせを生成しようとしています。以下に貼り付けたコードは機能しますが、非常に非効率的であると感じており、できるだけ高速にしたいと考えています。lowerupper

たとえば、"aab" と "zzz" の間で小文字のアルファベットのみを含むリストを生成したい場合、次のように出力されます。['aab', 'aac', 'aad', ..., 'zzy', 'zzz']

不明な点がある場合は、コメントを残してください。明確にします。ありがとう!

私が今働いているもの。

def generate_list(lower, upper):
    result = [lower]
    while lower != upper:
        if CHAR_LIST.index(lower[len(lower)-1:len(lower)]) + 1 < len(CHAR_LIST):
            lower = lower[:len(lower)-1] + CHAR_LIST[CHAR_LIST.index(lower[len(lower)-1:len(lower)]) + 1]
        else:
            new_lower = ""
            new_dig = 0
            inc_next = True
            for i in lower[::-1]:
                if i == CHAR_LIST[len(CHAR_LIST)-1] and inc_next:
                    new_lower += CHAR_LIST[0]
                    new_dig += 1
                else:
                    if inc_next:
                        inc_next = False
                        new_lower += CHAR_LIST[CHAR_LIST.index(i) + 1]
                    else:
                        new_lower += i
            if new_dig == len(lower):
                lower = str(CHAR_LIST[0])*int(len(lower)+1)
            else:
                lower = new_lower[::-1]
        result.append(lower)
    return result

編集:これは課題の一部であるため、開始点と終了点の長さが異なるリストも計算する必要があることを追加するのを忘れていました。たとえば、"a" と "zzz" の間のリストも計算する必要があります。改訂が遅れて申し訳ありません。これまでの創造的な回答に感謝します:)

4

3 に答える 3

2

必要以上に多くの作業を行っているため、コードがどのように機能するかを理解するのにかなりの時間がかかりました。これは、同じアルゴリズムの積極的に「pythonized」されたバージョンです。これは、現在のものよりもかなり高速になると思われます。

def generate_strings(value, bound, alpha):
    yield value
    while value != bound: # run until we have reached bound
        for i, c in enumerate(reversed(value)): # loop over the string in reverse
            if c != alpha[-1]: # can this character be incremented?
                # construct an incremented value
                value = value[:-1-i] + alpha[alpha.index(c)+1] + alpha[0]*i
                break # exit the for loop
        else: # run only if for loop ended without breaking
            value = alpha[0]*(len(value) + 1) # make a longer string
        yield value

この関数はジェネレーターであるため、リストの結果が必要な場合は、次の出力例のようにリスト コンストラクターに渡します。

>>> print(list(generate_strings("b", "cc", "abcd")))
['b', 'c', 'd', 'aa', 'ab', 'ac', 'ad', 'ba', 'bb', 'bc', 'bd', 'ca', 'cb', 'cc']

グローバル変数を使用するのではなく、一連の文字を関数の引数にしました。bound引数は、無限ジェネレーターを取得するために、またはその他の無意味な値にすることもできます(Noneただし、それlist()を短縮せずに に渡さないでください!)。これらの機能の両方の例を次に示します。

>>> from itertools import islice
>>> from string import ascii_lowercase
>>>
>>> print(list(islice(generate_strings("xyzzy", None, ascii_lowercase), 5)))
['xyzzy', 'xyzzz', 'xzaaa', 'xzaab', 'xzaac']

Python を初めて使用する場合、コード内で行われていることは明らかではないことがいくつかあります。

まず、文字列に多くの負のインデックスを使用します。-1これは、右端の文字から始めて、右から数えます。これだけでも、コードが大幅に簡素化されます (大量の がありましたx[len(x)-1])。

次に、組み込み関数enumerateとを使用reversedして文字列を右から左にループし、ループした文字数を追跡します。iこれはあなたが自分の価値観で何をしていたかについてだと思いますがnew_dig、もっと明確だと思います。Python には、便利なビルトイン ジェネレーターがたくさんあります。

最後に、breakステートメントを使用してfor早期にループを終了し、ブロックを使用してingelseなしで終了した場合を処理しました。breakこの種のelseon a loop は、最初に知ったときは役に立たないように思えましたが、ループの実行の大部分がbreakステートメントにヒットするという、このような状況では本当に便利です。

于 2013-01-31T05:00:58.073 に答える
2
import itertools
CHAR_LIST = list("abcdefghijklmnopqrstuvwxyz")

def generate_list(lower, upper):
    lower, upper = tuple(lower), tuple(upper)
    return ["".join(e) for e in itertools.product(CHAR_LIST, repeat=len(lower))
                  if e >= lower and e <= upper]

print generate_list("aab", "zzz")
于 2013-01-31T01:26:16.233 に答える
2

それがあなたが望むものだと私にitertools.productは思えます:

from string import ascii_lowercase
from itertools import product
all_combos = (''.join(x) for x in product(ascii_lowercase,repeat=3))
filtered = (s for s in all_combos if s > 'aaa')

itertools の素晴らしさに合わせて、ここではジェネレーターを使用しましたが、2 番目のジェネレーターをリスト内包表記に簡単に変換してリストを取得できます。また、それを関数に変換する方法が簡単にわかると信じています。ジェネレータ式に非常に単純な変更を加えたwith lowerand bounds (下限はすでに含まれています ;-) ...upperfiltered

于 2013-01-31T01:26:25.527 に答える