4

私は次の問題を解決するための高速で効率的な方法に取り組んできましたが、まだ、かなり遅いネストループ ソリューションを使用してしか解決できませんでした。とにかく、ここに説明があります：

長さ L の文字列があるとしましょう'BBBX'。から始まる、長さ L のすべての可能な文字列を見つけたいと思います'BBBX'。違いは最大で 2 桁、少なくとも 0 桁です。その上、新しい文字列を作成するときは、特定のアルファベットから新しい文字を選択する必要があります。

アルファベットのサイズは関係ないと思いますので、この場合のアルファベットは['B', 'G', 'C', 'X'].

したがって、いくつかのサンプル出力は、、、、などになります'BGBG'。'BGBC'最大'BBGX'2 つの置換を含む長さ 4 の文字列を使用したこの例では、私のアルゴリズムは 67 の可能な新しい文字列を見つけます。

この問題を解決するために使用しようとしていますがitertools、解決策を見つけるのに少し苦労しています。私itertools.combinations(range(4), 2)はすべての可能な位置を見つけるために使用しようとします。次に、すべての可能性を構築するためにproduct()fromを使用することを考えitertoolsていますが、何らかの方法で の出力からのインデックスに接続できる方法があるかどうかはわかりませんcombinations()。

4

2 に答える 2

2

これが私の解決策です。

最初の for ループは、実行する置換の数を示します。(0、1、または 2 - それぞれを調べます)

2 番目のループは、どの文字を変更するかを (インデックスによって) 示します。

3 番目のループでは、これらのインデックスで可能なすべての文字の変更が行われます。実際に文字を変更することを確認するロジックがいくつかあります (「C」を「C」に変更してもカウントされません)。

import itertools

def generate_replacements(lo, hi, alphabet, text):
    for count in range(lo, hi + 1):
        for indexes in itertools.combinations(range(len(text)), count):
            for letters in itertools.product(alphabet, repeat=count):
                new_text = list(text)
                actual_count = 0
                for index, letter in zip(indexes, letters):
                    if new_text[index] == letter:
                        continue
                    new_text[index] = letter
                    actual_count += 1
                if actual_count == count:
                    yield ''.join(new_text)

for text in generate_replacements(0, 2, 'BGCX', 'BBBX'):
    print text

その出力は次のとおりです。

BBBX GBBX CBBX XBBX BGBX BCBX BXBX BBGX BBCX BBXX BBBB BBBG BBBC GGBX
GCBX GXBX CGBX CCBX CXBX XGBX XCBX XXBX GBGX GBCX GBXX CBGX CBCX CBXX
XBGX XBCX XBXX GBBB GBBG GBBC CBBB CBBG CBBC XBBB XBBG XBBC BGGX BGCX
BGXX BCGX BCCX BCXX BXGX BXCX BXXX BGBB BGBG BGBC BCBB BCBG BCBC BXBB
BXBG BXBC BBGB BBGG BBGC BBCB BBCG BBCC BBXB BBXG BBXC
于 2013-11-12T03:02:13.333 に答える
1

あまりテストされていませんが、あなたが示した例では67が見つかりました。インデックスを製品に接続する簡単な方法は次のzip()とおりです。

def sub(s, alphabet, minsubs, maxsubs):
    from itertools import combinations, product
    origs = list(s)
    alphabet = set(alphabet)
    for nsubs in range(minsubs, maxsubs + 1):
        for ix in combinations(range(len(s)), nsubs):
            prods = [alphabet - set(origs[i]) for i in ix]
            s = origs[:]
            for newchars in product(*prods):
                for i, char in zip(ix, newchars):
                    s[i] = char
                yield "".join(s)

count = 0
for s in sub('BBBX', 'BGCX', 0, 2):
    count += 1
    print s
print count

注: FogleBird のものとの主な違いは、私が最初に投稿したことです - LOL ;-) アルゴリズムは非常に似ています。Mine は への入力を構築してproduct()、文字自体の置換が試行されないようにします。FogleBird では「アイデンティティ」置換を許可していますが、有効な置換がいくつ行われたかをカウントし、アイデンティティ置換が発生した場合は結果を破棄します。より長い単語とより多くの置換では、はるかに遅くなる可能性があります (潜在的にループの前後の時間len(alphabet)**nsubsとの差)。(len(alphabet)-1)**nsubs... in product():

于 2013-11-12T02:59:33.420 に答える