I found this site helpful:
http://n1b-algo.blogspot.com/2009/01/string-permutations.html
Here is my javascript implementation of the case where duplicate characters are allowed, but duplicate permutations are not (using the hash table method described in the blog):
function swapElts(arr, x, y) {
var temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
// arr is array of things (characters) to permute
// start is an index into arr
// res is a list of the resulting permutations
function permute(arr, start, res) {
if(arr.length == start)
res.push(arr.join("")); // save this permutation
else {
var hashtable = {};
for(var i = start; i < arr.length; i++) {
// if element arr[i] is already in hashtable, it is a repeated character,
// so do not create permutations of the rest of the arry for it
if(hashtable[arr[i]])
continue;
swapElts(arr, start, i);
permute(arr, start+1, res);
swapElts(arr, start, i);
hashtable[arr[i]] = 1; // puts element arr[i] into hashtable
}
}
return res;
}
function permuteString(str) {
return permute(str.split(""), 0, []);
}
permuteString is a wrapper around the recursive permute(). It simply calls permute() passing in the array of characters making up the string, the starting index of 0, and an empty array where results are put.