Tell us what’s happening:
I’m trying to solve this task all day and i got some progress but still fail checking.
Where can i check my code iterating it step by step ?
Your code so far
function permAlone(str) {
let arr = str.split("");
let a = 0;
let c = 1;
let b;
for (let j = 2; j < arr.length + 1; j++){
c *= j;
}
for (let o = 0; o < c; o++){
for (let s = 0; s < arr.length; s++){
b = arr.splice(s,1).join();
arr.splice(s+1,0,b);
let i = 1;
if(arr.every((e,i,a) => a[i] !== a[i-1])){
a++;
};
}
}
return a;
}
console.log(permAlone('aab'));
Your browser information:
User Agent is: Mozilla/5.0 (Windows NT 6.1; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/79.0.3945.88 Safari/537.36.
In the first loop i determine all possible permutations of string finding factorial of array length number - let o;
3.use let o as condition for second loop to check all possible permutations of the string.
4.inside next loop i’m doing permutations with splice method and checking for not repeating letters in array property every and if returned value is true i increase let a by 1 and go to next permutatioon.
i see that i somehow got over iteration and decreasing let c i almost got all checks passed but it is trying to fit answer to question which is not helpful for understanding. Thanks for your attention.
Ok. I paused to solve it by my way becasue i stucked.
Now when i’m trying just to fill array with premutations of string i got it full of the same string despite in console i see that mutation is going in resulted array it passes unchanged
function permAlone(str) {
let arr = str.split("");
let b;
let count = [];
for (let s = 0; s < arr.length - 1; s++){
b = arr.splice(s,1).join();
console.log(b);
arr.splice(s+1,0,b);
console.log(arr);
count.push(arr);
}
return count;
}
console.log(permAlone('abcde'));
Now i just want to fill array with permutations of string but i got array with the same version of string.
[ [ ‘b’, ‘c’, ‘d’, ‘e’, ‘a’ ],
[ ‘b’, ‘c’, ‘d’, ‘e’, ‘a’ ],
[ ‘b’, ‘c’, ‘d’, ‘e’, ‘a’ ],
[ ‘b’, ‘c’, ‘d’, ‘e’, ‘a’ ] ]
This problem used to be on the advanced algorithms section of the old FCC curriculum. I can understand why it’s been moved to a non-essential section of the new curriculum. It is very difficult to solve if you approach it in the wrong way.
The approach you are taking involves generating all possible permutations and then checking them to see if they are valid. You should not take this approach as your code will time out. The test case "zzzzzzzz" will have 8! (40320) possible permutations alone, which you are then nesting with additional loops. The iterations will quickly balloon making the execution time too long.
Instead, the problem is solvable using an inner recursive function with a global counter. The idea is that the recursive function builds up the string permutations but stops as soon as two consecutive characters are the same. If a string can be fully built with no consecutive repeats then the global counter can be incremented. At the end the global count is returned. This approach will dramatically reduce the number of iterations your code has to make.
But how would you know the next character without performing permutation? Don’t you still need same n! operation just to know the next character? I’m a bit lost…
The solution I am proposing would only check all permutations in a worst case scenario, where all the characters are different (e.g. "abcde").
The permutations are built up and checked one character at a time. As soon as two consecutive characters are found to be the same, the calculations for that particular set of permutations can cease as none will satisfy the condition of no repeats.
This can be achieved through a recursive function, which generates the permutations and only calls itself again if the current character being examined is different from the previous one. If this works for the full length of the string permutation then the global count can be incremented, as the string is confimed to have no consecutive repeats.
I found all possible permutations of a string with not very gloomy algorithm which i found on stackover though something wrong with my resulted array because it has no length and so can’t be iterated
function permAlone(string) {
if (string.length < 2) return string;
let permutations = [];
for (var i = 0; i < string.length; i++) {
var char = string[i];
if (string.indexOf(char) != i) continue;
var remStr = string.slice(0, i) + string.slice(i + 1, string.length);
for(var elem of Array.from(permAlone(remStr))){
permutations.push(char + elem);
}
}
return permutations;
}
console.log(permAlone('aadcrb'));
All arrays have length and could be iterated. Here are couple remarks regarding algorithm:
function permAlone(string) {
// you might want to return [string] instead for consistency
if (string.length < 2) return string;
let permutations = [];
for (let i = 0; i < string.length; i++) {
const char = string[i];
// This line makes no sense and this statement will never be true
if (string.indexOf(char) != i) continue;
// No need to do string.slice(i + 1, string.length), just string.slice(i + 1) would be enough
const remStr = string.slice(0, i) + string.slice(i + 1, string.length);
// permAlone returns either String or Array, both iterable with for-of loop, so there is no need for Array.from() method here
for(let elem of Array.from(permAlone(remStr))){
permutations.push(char + elem);
}
}
return permutations;
}
If you fix remarks it would be perfect permutation algorithm, the one you shall memorize
Ok, i did it though i still don’t understand what exactly it changed but where i have to implement regex checking of permutations. Now it is not working because of same problem with array
let a = 0;
let reg = /(.)\1+/;
permutations.forEach(function(elem, i){
if(elem[i].match(reg)) a++;
})
