title: Heap's algorithm for permutations
body: <p>I'm preparing for interviews and I'm trying to memorize Heap's algorithm:</p>
  <pre class="lang-pascal prettyprint-override"><code>procedure generate(n : integer, A : array of any):
      if n = 1 then
            output(A)
      else
          for i := 0; i &lt; n; i += 1 do
              generate(n - 1, A)
              if n is even then
                  swap(A[i], A[n-1])
              else
                  swap(A[0], A[n-1])
              end if
          end for
      end if
  </code></pre>
  <p>This algorithm is a pretty famous one to generate permutations. It is concise and fast and goes hand-in-hand with the code to generate combinations.</p>
  <p>The problem is: I don't like to memorize things by heart and I always try to keep the concepts to &quot;deduce&quot; the algorithm later.</p>
  <p>This algorithm is really not intuitive and I can't find a way to explain how it works to myself.</p>
  <p>Can someone please tell me <em>why</em> and <em>how</em> this algorithm works as expected when generating permutations?</p>