Skip to content

Instantly share code, notes, and snippets.

@olveirap
Created February 15, 2017 00:48
Show Gist options
  • Save olveirap/0dcf7a0b6cd663a40897925db18854d5 to your computer and use it in GitHub Desktop.
Save olveirap/0dcf7a0b6cd663a40897925db18854d5 to your computer and use it in GitHub Desktop.
Javascript implementation of Heap's Algorithm for combinatorics
//http://stackoverflow.com/questions/872310/javascript-swap-array-elements
Array.prototype.swap = function (x,y) {
var b = this[x];
this[x] = this[y];
this[y] = b;
return this;
}
//https://en.wikipedia.org/wiki/Heap's_algorithm
function generate(n){
var combinations = [];
var A = [];
var c = [];
for(var i = 0; i < n; i++){
c.push(0);
A.push(i+1);
}
combinations.push(A);
i = 0;
while(i < n){
if(c[i] < i){
if(i % 2 == 0){
A.swap(0, i);
}else{
A.swap(c[i], i);
}
combinations.push(A);
c[i]++;
i = 0;
}else{
c[i] = 0;
i++;
}
}
return combinations;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment