0

I'm wanting to generate all possible permutations of the letters A - G (seven) and Heap's algorithm allegedly makes this possible.

However, when I look at the pseudo code from the Wikipedia page I see this:

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
    else
        for i := 0; i < n - 1; 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
        generate(n - 1, A)
    end if

....and have no idea what it means.

So, I know that if I have seven letters (A-G) it'll apperently find all the possible permutations of the first six letters while the letter at the end stays the same.

Meaning, it'll find all possible permuations of A-F while G is on the end, and do that until each letter has been on the end.

Given, I have seven letters, that means "N" is odd, and thus I always switch the end letter (seventh one) with the letter that is in the first slot.

But (and I know this isn't how it works, but it's all I'm getting from it) won't that just result in the same two letters being swapped constantly and no diffent permutations?

I've scoured google results for the past 4 hours and can't find anything that explains line by line the above pseudo-code.

Help is greatly appreciated!!

trincot
  • 317,000
  • 35
  • 244
  • 286
Edson
  • 255
  • 1
  • 3
  • 18
  • do you have any javascript code to share? – Jaromanda X Nov 08 '16 at 02:25
  • 1
    Because the code calls `generate` before it does the swap, the letter in `A[0]` is not constant. Evidently, when `n` is odd, the letter at `A[0]` goes through all possibilities, whereas when `n` is even, you need to take the letter at `A[i]` to get all of the possibilities. Not sure how Heap proved that works for all values of `n`. – user3386109 Nov 08 '16 at 02:52
  • There's a diagram on the wikipedia page that shows all the swaps. – Barmar Nov 08 '16 at 02:55
  • @user3386109 what exactly does generate mean/do in this context? – Edson Nov 08 '16 at 05:39
  • @JaromandaX No, I'm just wanting to understand the pseudo code so that I can use it later in javascript. – Edson Nov 08 '16 at 05:42
  • @Barmar Yeah, I saw that, but I don't see the way the pseudo code executes what's shown in the diagram. – Edson Nov 08 '16 at 05:44
  • `generate` is the name of the procedure, so the calls to `generate` are [recursive calls](https://en.wikipedia.org/wiki/Recursion_(computer_science)). Imagine that the top level call is `generate( 5, array )`. That requests an array of 5 elements be shuffled. The next level call would be `generate( 4, array )` which shuffles the first 4 entries in the array, leaving the last one undisturbed. – user3386109 Nov 08 '16 at 05:45
  • related http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string – Tomer W Nov 08 '16 at 08:04
  • @Edson Try executing the pseudo-code by hand on paper, you should see the way it works. – Barmar Nov 08 '16 at 17:34

0 Answers0