June 5, 2015 - algorithms javascript

# Solving permutations with Heap's Algorithm in Javascript

Xavier Geerinck

A friend of mine had just gotten the question to find every combination for a given array in [1, 2, 3].
When analyzing this question I found out that this is actually a simple permutation that has to be generated with the use of Javascript. Lucky for me we had just had the course Discrete math in school so we saw some algorithms that could do this. The algorithm that I used for this is **Heap's algorithm**.

## Heap's Algorithm

Heaps algorithm is an algorithm that computes every single permutation of a given set of elements. The algorithm is basically going to swap elements based on the iteration k we are in for the current size n. If this iteration k is even then we will swap the kth element with the last element, and else we will swap the last element with the first element.

For more details about this algorithm please check Robert Sedgewick's book.

## Javascript

Programming this in Javascript can be done by following the pseudocode that we can find on sites such as wikipedia or just following the details given in Robert Sedgewick's book.

### Pseudocode

generate (n, arr)if n = 1output arrelsefor i = 0; i < n; i += 1generate (n - 1, arr)if n is evenswap(arr[i], arr[n - 1])elseswap(arr[0], arr[n - 1])

### Javascript

// Purpose is to create every permutation from the elements in the array// We can do this by using Heap's algorithmvar start = [1, 2, 3];// Get the permutationsgenerate(start.length, start);// Generate the permutation for a given n (amount of elements) and a given arrayfunction generate(n, arr) {// If only 1 element, just output the arrayif (n == 1) {console.log(arr);return;}for (var i = 0; i < n; i+= 1) {generate(n - 1, arr);// If n is evenif (n % 2 == 0) {swap(arr, i, n - 1);} else {swap(arr, 0, n - 1);}}}function swap(arr, idxA, idxB) {var tmp = arr[idxA];arr[idxA] = arr[idxB];arr[idxB] = tmp;}

### Output

for the array [1, 2, 3] as used in the solution I get the following solution.

[2, 3, 1][3, 2, 1][1, 2, 3][2, 1, 3][3, 1, 2][1, 3, 2][2, 3, 1][3, 2, 1]