title: Heap's algorithm permutation generator
body: <p>I need to iterate over permutations of a tuple of integers. The order has to be generated by swapping a pair of elements at each step.</p>
  
  <p>I found the Wikipedia article (<a href="http://en.wikipedia.org/wiki/Heap%27s_algorithm">http://en.wikipedia.org/wiki/Heap%27s_algorithm</a>) for Heap's algorithm, which is supposed to do this. The pseudocode is:</p>
  
  <pre><code>procedure generate(n : integer, A : array of any):
      if n = 1 then
          output(A)
      else
          for i := 1; i ≤ n; i += 1 do
              generate(n - 1, A)
              if n is odd then
                  j ← 1
              else
                  j ← i
              swap(A[j], A[n])
  </code></pre>
  
  <p>I tried to write a generator for this in python:</p>
  
  <pre><code>def heap_perm(A):
      n = len(A)
      Alist = [el for el in A]
      for hp in _heap_perm_(n, Alist):
          yield hp
  
  
  def _heap_perm_(n, A):
      if n == 1:
          yield A
      else:
          for i in range(1,n+1):
              for hp in _heap_perm_(n-1, A):
                  yield hp
              if (n % 2) == 1:
                  j = 1
              else:
                  j = i
              swap = A[j-1]
              A[j-1] = A[n-1]
              A[n-1] = swap
  </code></pre>
  
  <p>This produces permutations in the following order (for input of [0,1,2,3]):</p>
  
  <pre><code>0,1,2,3
  1,0,2,3
  2,0,1,3
  0,2,1,3
  1,2,0,3
  2,1,0,3
  3,1,2,0
  
  and so on
  </code></pre>
  
  <p>This seems fine until that last step, which isn't a swap of one pair.</p>
  
  <p>What am I doing wrong?</p>