3

私はインターネットでいくつかのプログラミングの問題に答えていましたが、この問題に興味があります。問題は次のように定義されます。

このコードは、文字列のすべての順列を辞書順に出力します。何かがおかしい。1行を変更または追加して、見つけて修正してください！

入力：

入力は、間にスペースを入れない小文字の文字列を含む 1 行で構成されます。その長さは最大 7 文字で、その文字は辞書順にソートされています。

出力：

文字列のすべての順列が各行に 1 つずつ出力され、辞書式にリストされています。

def permutations():
global running
global characters
global bitmask
if len(running) == len(characters):
    print(''.join(running))
else:
    for i in xrange(len(characters)):
        if ((bitmask>>i)&1) == 0:
            bitmask |= 1<<i
            running.append(characters[i])
            permutations()
            running.pop()

raw = raw_input()
characters = list(raw)
running = []
bitmask = 0
permutations()

誰かが私に答えて、それがどのように機能するかを説明できますか? 私はビットマスキングのアプリケーションにあまり詳しくありません。ありがとうございました。

4

1 に答える 1

2

次の行を追加して、ビットマスクをビット 0 に戻す必要があります。

bitmask ^= 1<<i

コード：

def permutations():
    global running
    global characters
    global bitmask
    if len(running) == len(characters):
        print(''.join(running))
    else:
        for i in xrange(len(characters)):
            if ((bitmask>>i)&1) == 0:
                bitmask |= 1<<i
                running.append(characters[i])
                permutations()
                bitmask ^= 1<<i  #make the bit zero again.
                running.pop()

raw = raw_input()
characters = list(raw)
running = []
bitmask = 0
permutations()

説明:
ビットマスクは、ビットのストリングとして扱われる整数です。あなたの場合、この文字列の長さは入力文字列の長さと同じです。

この文字列の各位置は、対応する文字が部分的に構築された文字列に既に追加されているかどうかを示します。

このコードは、空の文字列から始まる新しい文字列を作成することによって機能します。文字が追加されるたびに、ビットマスクがそれを記録します。次に、さらに文字を追加するために、文字列が再帰の奥深くに送られます。コードが再帰から戻ると、追加された文字が削除され、ビットマスク値が元の値に戻される必要があります。

マスキングの詳細については、こちらを参照してください。http://en.wikipedia.org/wiki/Mask_%28computing%29

編集：
入力文字列が「abcde」で、コード実行中の任意の時点でのビットマスクが「00100」であるとします。これは、文字 'c' のみが部分的に作成された文字列に追加されたことを意味します。したがって、文字「c」を再度追加するべきではありません。
「if」条件((bitmask >> i) & 1) == 0は、ビットマスクの i 番目のビットが設定されているかどうか、つまり、文字列に i 番目の文字がすでに追加されているかどうかをチェックします。追加されていない場合のみ、文字が追加されます。それ以外の場合は追加されません。

ビット操作が初めての場合は、インターネットでこのトピックを調べることをお勧めします。

于 2014-11-22T07:41:51.873 に答える