使用位掩码生成排列

Question

使用位掩码生成排列

pythonalgorithmpermutationbitmasklexicographic

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

有人能为我回答这个问题并解释一下它是如何工作的吗？我对位掩码的应用不是很熟悉。谢谢。

- kalev25

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Abhishek Bansal · Accepted Answer

你需要添加以下代码来将位掩码的第0位设置为0：

bitmask |= 1;

请注意保留HTML标签，同时使翻译内容易于理解。

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个字符是否已添加到字符串中。如果没有添加，则仅追加字符，否则不添加。

如果您对位运算不熟悉，我建议您在互联网上查找此主题的相关信息。