title: Generating permutations using Bitmasking
body: <p>I was answering some programming problems in the internet and this problem interests me. The problem is defined as follows:</p>
  
  <blockquote>
    <blockquote>
      <p>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!</p>
    </blockquote>
  </blockquote>
  
  <p>Input:</p>
  
  <p>The input consists of a single line containing a string of lowercase characters with no spaces in between. Its length is at most 7 characters, and its characters are sorted lexicographically.</p>
  
  <p>Output:</p>
  
  <p>All permutations of the string printed one in each line, listed lexicographically.</p>
  
  <pre><code>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&gt;&gt;i)&amp;1) == 0:
              bitmask |= 1&lt;&lt;i
              running.append(characters[i])
              permutations()
              running.pop()
  
  raw = raw_input()
  characters = list(raw)
  running = []
  bitmask = 0
  permutations()
  </code></pre>
  
  <p>Can somebody answer it for me and explain how it works? I am not really familiar in the applications of bitmasking. Thank you.</p>