I've built a thesaurus-application in React that fetches data from a web-dictionary API and renders definitions, synonyms, and antonyms as collapsible lists when a user searches a word. I'd like to add a feature that will display all of the valid anagrams of a word that is searched (this isn't the problem right now, however).
I have written a recursive algorithm that finds all of the possible permutations of any given input, based on the number of possible permutations for that word. The only problem is, I encounter a RangeError when the input is any greater than 6 letters long. I know that my algorithm can and will find all permutations of an input greater than 6 characters long, but is hindered by the maximum-size of the call-stack.
I've attempted to use multiple different non-recursive algorithms that accomplish the same purpose from various other sources I've stumbled upon, and all but one encounter the same issue. If possible, however, I would like to refactor my solution to be viable, rather than copying the one working solution that I have found. I will display both my solution and the working solution for informational purposes.
My solution:
/* These next two helper functions can be ignored, I've included them in case
of your curiosity. However, they are unimportant to the problem at hand.
Both functions merely determine the total number of possible permutations for a given
input, which I use to determine how many times my final function should recurse */
// Helper function 1
const hasDuplicates = (str) => {
const letters = {};
str.split('').forEach(letter => {
if (letters[letter] !== undefined) letters[letter] ;
if (letters[letter] === undefined) letters[letter] = 1;
});
for (let key in letters) {
let currLetter = letters[key];
if (currLetter > 1) return letters;
};
return false;
};
// Helper function 2
const numPermutations = (str) => {
if (hasDuplicates(str) === false) {
let multiplier = 1;
for (let i = 1; i <= str.length; i ) multiplier *= i;
return multiplier;
};
const letters = hasDuplicates(str);
let multiplier = 1;
let divisor = 1;
let visited = new Set();
for (let i = 1; i <= str.length; i ) {
let currLetter = str[i];
if (letters[currLetter] > 1 && !visited.has(currLetter)) {
for (let j = 1; j <= letters[currLetter]; j ) {
divisor *= j;
};
visited.add(currLetter);
};
multiplier *= i;
};
return (multiplier / divisor);
};
// Final recursive function
const permutations = (string, finalArray = [], i = 0, visited = new Set()) => {
/* If the input consists of only two values and both are identical, we know that
further evaluation is unnecessary. */
if (string.length === 2) {
if (string.split('')[0] === string.split('')[1]) {
finalArray.push(string);
return finalArray;
};
};
if (string.length <= 2 && finalArray.length === string.length) return finalArray;
// Call to previous helper function which determines number of times we must recurse
const maxPermutations = numPermutations(string);
if (i === maxPermutations) return finalArray;
const splitString = string.split('');
// Scramble the letters of the string and rearrange them in a random order
for (let i = splitString.length - 1; i > 0; i--) {
let randNum = Math.floor(Math.random() * (i 1));
let replacement = splitString[i];
splitString[i] = splitString[randNum];
splitString[randNum] = replacement;
};
if (!visited.has(splitString.join(''))) {
/* If we don't already have this random variation of the string in our array,
push it into our final array, add it to the set of strings we've encountered,
and increment our index variable to work towards the base case */
finalArray.push(splitString.join(''));
visited.add(splitString.join(''));
return permutations(string, finalArray, i = 1, visited);
};
/* If we have encountered the latest random variation of our string,
recurse without incrementing our index (does not work toward base case) */
return permutations(string, finalArray, i, visited);
};
Again, this works great for inputs less than 7 characters long. However, anything longer, and the maximum call stack size is exceeded. I am including the one solution I've found that works around this problem below, in hope that it may be able to shed light on a possible workaround for my solution. That being said, I don't understand how this solution works or why it works, only that it does. I'll use it in my application as a last resort, but I prefer to use my own work over the work of someone else.
function permutes(string) {
var s = string.split('').sort();
var res = [s.join('')]
while(true) {
var j = s.length - 2;
while (j != -1 && s[j] >= s[j 1])
j--;
if(j == -1)
break;
var k = s.length - 1;
while(s[j] >= s[k])
k--;
[s[j], s[k]] = [s[k], s[j]];
var l = j 1, r = s.length - 1;
while (l<r) {
[s[l], s[r]] = [s[r], s[l]];
l ;
r--;
}
res.push(s.join(''));
}
return res;
}
CodePudding user response：
You should use a function named nextPermutation that only returns the next permutation in lexical order. This will save tons of memory.
Considering this answer all it takes is translate numbers to letters. Let's try.
var nextPermutation = function(word) {
var nums = word.split('');
function swap(index1, index2) {
var temp = nums[index1]
nums[index1] = nums[index2]
nums[index2] = temp;
}
function next_bigger_from(pos) {
var current = nums[pos];
var result = -1;
var min = null;
for (var i = pos 1; i < len; i ) {
if (nums[i] > current) {
result = i;
min = nums[i];
}
}
return result;
}
function sort_from(pos) {
for (var i = pos; i < len - 1; i ) {
for (var j = i 1; j < len; j ) {
if (nums[i] > nums[j]) {
swap(i, j)
}
}
}
}
var len = nums.length;
if (len < 2) {
console.log("" nums)
return;
}
var rotator = 2; // from right
while (rotator <= len) {
var pos = len - rotator;
var pos2 = next_bigger_from(pos);
if (pos2 == -1) {
rotator = 1;
continue;
}
swap(pos, pos2);
sort_from(pos 1);
return nums.join("");
}
nums = nums.sort();
return nums.join("");
};
var str = "ABCDEFGH"
for (var i = 0; i < 100; i ) {
console.log(str)
str = nextPermutation(str)
}.as-console-wrapper {max-height: 100% !important}CodePudding user response：
You are trying to calculate all the permutations via random sampling with replacement. This can be modelled by the Coupon Collector's Problem. The expected number of trials to get them all via this method grows somewhat faster than n * log (n), where n is the total number of items you want to fetch. If you have 7 (all distinct) characters, the number of permutations will be 7!, or 5040, which means the expected number of tries before you hit them all is
[1, 2, 3, ... 5040] .reduce ((n, f) => n 5040 / f, 0)
which is a bit over 45876. This is smaller if there are duplicated letters, of course.
Doing this recursively, means that you will likely hit recursion depth limits doing this. If you switched to an iterative loop, this would probably work for seven, but you will still quickly hit significant limits with such a technique.
If you want all permutations, but in a random order, I would suggest that you generate them all and shuffle the results.
Note that you could definitely simplify both your counting function and your generation function. To count them, we can use the mathematical fact that if there are a A's, b B's, ... and k K's the number of total permutations is
(a b ... k)! / (a! * b! * ... * k!)
so with a simple count function that, for instance, converts "ABCDBBC" to {A: 1, B: 3, C: 2, D: 1}, and a trivial factorial function, we could simply write that fairly simply.
I know you'd prefer to use your own code, but if you want to see my implementation of this idea, you can expand this snippet:
const factorial = (n) => n < 2 ? 1 : n * factorial (n - 1)
const count = ([...s]) =>
s .reduce ((a, c) => ((a [c] = (a[c] || 0) 1), a), {})
const numPermutations = (s) =>
Object .values (count (s)) .reduce ((n, f) => n / factorial (f), factorial (s .length))
console .log (numPermutations ('ABCDBBC')) //=> 420
// We probably don't call it enough to matter, but `factorial` is a good candidate for
// memoization. If you want to do that, it's simple enough:
//
// const factorial = ((memo = {}) =>
// (n) => n in memo ? memo [n] : memo [n] = n < 2 ? 1 : n * factorial (n - 1)
// )()To directly find all the permutations, we might use a variant of the technique I used in another answer. That one doesn't take into account multiplicities. We could tweak it to stop collecting when we might start hitting duplicates. Again, expand the snippet if you want to see my implementation, with an explanation in the comments.
// Here `excluding` returns a copy of an array with the element at a particular index
// removed. Our `permutations` function returns a result containing only an empty array if
// the input is empty. Otherwise it loops through the letters, and, if it's the first
// instance of that letter removing it from consideration, recurring with the remaining
// letters and for each result, prepending this first letter to it. If it's not the first
// instance, we just return an empty result. This last is the twist from the original which
// blindly did the recursive step, and thus for `"AAB"` would return all six possible
// permutations, even though there are duplicates (`["AAB", "ABA", "AAB", "ABA", "BAA",
// "BAA"]`). By testing `xs .indexOf (x) == i`, we eliminate large swaths of the
// potential output.
const excluding = (i) => (xs) =>
[... xs .slice (0, i), ... xs .slice (i 1)]
const permutations = ([...xs]) =>
xs .length == 0
? [[]]
: xs .flatMap ((x, i) =>
xs .indexOf (x) == i ? permutations (excluding (i) (xs)) .map (p => x p) : []
)
console .log (permutations ('ABCDBBC')).as-console-wrapper {max-height: 100% !important; top: 0}