python - 使用位掩码生成排列

Question

我在网上回答了一些编程问题，这个问题让我很感兴趣。问题定义如下:

This code prints all the permutations of the string lexicographically. Something is wrong with it. Find and fix it by modifying or adding one line!

输入:

输入由单行组成，其中包含一串小写字符，中间没有空格。其长度最多为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()

有人可以为我解答并解释它是如何工作的吗？我对位掩码的应用不是很熟悉。谢谢。

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 个字符是否已被设置添加到字符串中。如果不添加，则只添加字符，否则不添加。

如果位操作对您来说是新的，那么我建议您在 Internet 上查找此主题。