Skip to content

Instantly share code, notes, and snippets.

@kristopolous
Last active August 28, 2016 16:01
Show Gist options
  • Save kristopolous/4617410 to your computer and use it in GitHub Desktop.
Save kristopolous/4617410 to your computer and use it in GitHub Desktop.
The Steinhaus-Johnson-Trotter permutation algorithm in Javascript
function permute(array) {
// Identity
if(!array.length) {
return [];
}
var ret = [array],
len = array.length,
modlen = len - 1,
mover = array[modlen],
which,
subset = permute(array.slice(0, -1)),
permlen = subset.length;
for(var iy = 0; iy < permlen; iy++) {
which = subset[iy];
if(iy % 2) {
for(var ix = 0; ix <= modlen; ix ++) {
ret.push(which.slice(0, ix).concat([mover], which.slice(ix)));
}
} else {
for(var ix = modlen - 1; ix >= 0; ix --) {
ret.push(which.slice(0, ix).concat([mover], which.slice(ix)));
}
}
}
return ret;
}
@nam1603
Copy link

nam1603 commented Mar 20, 2015

The result is 22 values when i input '1234'. It is wrong. In this case, it has 24 values. Please check again

@kristopolous
Copy link
Author

thanks. silly thing is that I was looking for this a couple weeks ago and ran into my own old code and saw your comment and thought "oh this bozo implementation is wrong. I can't use it". And it took me a while to realize that it was MY implementation and I was the bozo here.

Anyway, I should fix this regardless ... the implementation I ended up using I lifted from a "framework" thing that was really top-heavy

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment