Heap's Algorithm step by step.md

Heap's Algorithm step by step

Take the example of generating the permutations of the array ['a', 'b', 'c', 'd'].

Assume that the function named generate(n, arr) with two parameters: n is the length of the array; and the arr is the array to be dealt with.

And the calling statement would be: generate(4, ['a', 'b', 'c', 'd']);.

There's a for loop inside the algorithm. So:

generate(4, ['a', 'b', 'c', 'd']);

1. for: i = 0

   • generate(3, ['a', 'b', 'c', 'd']);

     1. for: i = 0

        • generate(2, ['a', 'b', 'c', 'd']);

          1. for: i = 0

             • generate(1, ['a', 'b', 'c', 'd'])

               • console.log(arr) would be ["a", "b", "c", "d"];
               • return;

             • swap arr(i) and arr[n - 1], the array swapped to be ['b', 'a', 'c', 'd']

          2. for: i = 1

             • generate(1, ['b', 'a', 'c', 'd']);

               • console.log(arr) would be ["b", "a", "c", "d"];
               • return;

             • swap arr(i) and arr[n - 1], the array swapped to be ['b', 'a', 'c', 'd'],with no changes made actually.

        • swap arr(0) and arr[n - 1],the array be ['c', 'a', 'b', 'd']

     2. for: i = 1

        • generate(2, ['c', 'a', 'b', 'd']);
        • swap

     3. for: i = 2

        • generate(2, array);
        • swap

   • swap

2. for: i = 1

   • generate(3, array);
   • swap

3. for: i = 2

   • generate(3, array);
   • swap

4. for: i = 3

   • generate(3, array);
   • swap

Also a much more better picture can be found here.

Thank you for this, it helped me understand the algorithm.