Tell us what’s happening:
Greetings! I tried using Heap’s algorithm for this puzzle, however the number of permutations created by the algorithm vs the mathematical calculation are different, for example:
“aabb” is calculated at 4! = 24 permutations, however my Heap’s algorithm only logs 21. Any idea why it doesn’t account for every permutation?
Your code so far
function permAlone(str){
var perms = [];
let arr = str.split('');
//add a prototype to swap letters in array
Array.prototype.swap = function (x,y) {
var b = this[x];
this[x] = this[y];
this[y] = b;
return this;
}
//Deploys Heap's algorithm
function generate(n,arr){
if (n === 1){
perms.push(arr.join(''));
}
else {
for (var i = 0; i < n-1; i++){
generate(n-1, arr);
if (n % 2 == 0){
perms.push(arr.swap(i, n-1).join(''));
}
else {
perms.push(arr.swap(0,n-1).join(''));
}
}
}
}
generate(str.length,arr);
//check Heap
//console.log(perms.length);
//check Factorial
//console.log(getPerms(str,false));
let result = perms.filter(word => {
return /([a-z])(\1)/g.test(word) == false;
});
return result.length;
//-----------This function is not actually used, I used it as a benchmark for the correct num of permutations---------------------------------------
//loops through the length of str, and pushes index value into array
function getPerms(str,num){
if (str){
let arr = [];
for (var i = str.length; i > 0; i--){
arr.push(i);
}
//calc perms by reducing to get factorial
return arr.reduce((a,b) => a*b);
}
//does the same, just replaces str w/ number
else if (num){
let arr = [];
for (var i = num; i > 0; i--){
arr.push(i);
}
return arr.reduce((a,b) => a*b);
}
}
//---------------------------------------------
}
permAlone("abcdefa");
Your browser information:
User Agent is: Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/68.0.3440.106 Safari/537.36.
Link to the challenge:
https://learn.freecodecamp.org/coding-interview-prep/algorithms/no-repeats-please/