使用Bitmasking生成排列

Question

我在網上回答了一些編程問題，這個問題讓我感興趣。問題是定義如下：

這個代碼打印出所有字符串的字典順序排列。它有什麼問題。通過修改或添加一行來查找並修復它！

輸入：

輸入由含有的小寫字符的字符串與在之間沒有空格的單一生產線。其長度最多爲7個字符，其字符按字典順序排序。

輸出：

印刷一個在每行中的字符串，字典順序列出的所有排列。

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() 

有人可以爲我回答並解釋它是如何工作的嗎？我對bitmasking的應用並不熟悉。謝謝。

Answer 1

你應該通過增加線使位掩碼位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個字符是否已被添加到字符串中。如果沒有添加，只有字符被附加，否則不會。

如果位操作對你來說是新的，那麼我建議你在互聯網上查看這個主題。