Skip to content

Instantly share code, notes, and snippets.

@customcommander
Last active April 15, 2019 16:28
Show Gist options
  • Save customcommander/e9af9da584ff3a33f5ed to your computer and use it in GitHub Desktop.
Save customcommander/e9af9da584ff3a33f5ed to your computer and use it in GitHub Desktop.
Return all permutations of a string
/**
* Return all permutations of given string.
*
* @example
* permute('abc');
* //=> ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
* @param str {String}
* @return {Array}
*/
function permute(str) {
var ret = [];
// permutation for one or two characters string is easy:
// 'a' -> ['a']
// 'ab' -> ['ab', 'ba']
if (str.length == 1) return [str];
if (str.length == 2) return [str, str[1]+str[0]];
// otherwise combine each character with a permutation
// of a subset of the string. e.g. 'abc':
//
// 'a' + permutation of 'bc'
// 'b' + permutation of 'ac'
// 'c' + permutation of 'ab'
str.split('').forEach(function (chr, idx, arr) {
var sub = [].concat(arr); // "clone" arr
sub.splice(idx, 1);
permute(sub.join('')).forEach(function (perm) {
ret.push(chr+perm);
});
});
return ret;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment