3

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

此代码按字典顺序打印字符串的所有排列。它有问题。通过修改或添加一行来查找并修复它！

输入：

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

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

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 回答