Implementing Heap Algorithm of Permutation in JavaScript

Implementing a Heap Algorithm to find permutation of a set of numbers

Image for post
Image for post
No. of ways first box can be filled: nNo. of ways second box can be filled: (n — 1)No. of ways third box can be filled: (n — 2)No. of ways fourth box can be filled: (n — 3)No. of ways rth box can be filled: (n — (r — 1))Therefore, no. of ways of filling in r boxes in succession can be given by:n * (n — 1) * (n — 2) * (n-3) * . . . * (n — (r — 1))which matahematically simplifies to n! / (n — r)!

Why we need Heap’s Algorithm at all

Select A
Select B, yielding AB
Select C, then D, yielding ABCD —
procedure generate(n : integer, A : array of any):
if n = 1 then
for i := 0; i < n - 1; i += 1 do
generate(n - 1, A)
if n is even then
swap(A[i], A[n-1])
swap(A[0], A[n-1])
end if
end for
generate(n - 1, A)
end if
1. Permute the elements in positions 1 to n−1 by applying this algorithm to those elements.2. Apply the following steps n−1 times. Increment counter i=1 after each iteration.3. Swap element in position n with one of the other elements in the following way.A. If n is odd, swap elements in positions 1 and n. For odd-length permutations, the n-1 swap is always done with the first element.B. If n is even, swap elements in position i and n.  For even-length permutations, the n-1 swap is done with the i-th element, where i is a counter from position 0 to n-2 that increments every time we do this.

Written by

DataScience | ML | 2x Kaggle Expert. Ex Fullstack Engineer and Ex International Financial Analyst.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store