Skip to content

Instantly share code, notes, and snippets.

@cutthroat

cutthroat/gist:4957198

Created February 14, 2013 23:02
Show Gist options
  • Save cutthroat/4957198 to your computer and use it in GitHub Desktop.
Save cutthroat/4957198 to your computer and use it in GitHub Desktop.
Download ZIP
Heap's method for generating permutations
Raw
gistfile1.js
// Heap's method, see Sedgewick (1977)
function eachPerm(a, callback, target) {
var n = a.length;
var c = new Array(n);
var j = n;
while (j--) { c[j] = 0; }
var m = 0;
callback.call(target, a, m++);
var i = 1;
do {
if (c[i] < i) {
j = (i % 2 ? c[i] : 0);
var x = a[j]; a[j] = a[i]; a[i] = x;
++c[i]; i = 1;
callback.call(target, a, m++);
}
else {
c[i++] = 0;
}
} while (i < n);
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment