I’m currently working through the Advanced Algorithm Scripting, and after many hours of banging my head against the wall, I was able to complete No Repeats Please. This one has been by far the most difficult for me. At first I thought there must be some correlation between the total characters and the number of repeating characters. It seemed to work at first, take (“aab”) = 6 total perms and 2 non-repeating ones, so 1/3 and (“aabc”) = 24 perms and 12 non-repeating ones (1/2). However this quickly falls apart with stings like (“aabb”) and (“abcdefa”). So I gave up on trying to find an easy mathmatical solution and desided to just generate all possible perms. Sounded a lot easier then it was. It ended up taking me hours to figure out an algorithm that would allow me to generate all perms regardless of length.
Anyways I ended up using a recursive function that is very slow for larger strings, but it works. So I would love to get some feedback on my code and maybe see how others have completed this.
Thanks in advance
function rotateArr(arr,from)
//move the value at 'from' to the end of 'arr'
{
var a = arr.splice(from,1);
arr.push(a[0]);
}
var sameAs = [];
var count = 0;
function compare(arr)
{
//Convert array to string
var str=arr.toString();
str=str.replace(/,/g,""); //Remove ,
for(var i=0;i<sameAs.length;i++){
str=str.replace(sameAs[i][0],sameAs[i][1]);//Replace the numbers that represent dups with chars
}
for(var i=0;i<sameAs.length;i++){
if(str.match(""+sameAs[i][1]+sameAs[i][1])!==null){ return; } //Look for any chars that appear twice in a row
}
count++; //if none found increase count
return;
}
function recPerm(arr,len)
{
var cpy=arr.slice(0);
//Create a copy of the passed in array to ensure we do not change the original
for(var i=0;i<len;i++)
{
if(len>3){ recPerm(cpy,len-1); }
else
{
compare(cpy);
rotateArr(cpy,cpy.length-2); //swap last two
compare(cpy);
rotateArr(cpy,cpy.length-2); //Restore last two
}
rotateArr(cpy,cpy.length-len);
}
}
function permAlone(str)
{
if(str.length===1){ return 1; }
var skip=false;
//Ensure all global variables are reset
count = 0;
sameAs = [];
//Fill in ‘sameAs’ array with format [index#,“char”]
for(var i=0;i<str.length-1;i++)
{
skip=false;
for(var b=i+1;b<str.length;b++)
{
if(str[i]===str[b])
{
if(!skip){ sameAs.push([""+i,str[i]]); skip=true; }
sameAs.push([""+b,str[b]]);
}
}
}
var baseArray = [];
//Create an Array of numbers the same length as out string
//This will be used to ensure that every char has a unique value
for(var i=0;i<str.length;i++){ baseArray.push(i); }
//Call recursive function to walk through all possible permutations
recPerm(baseArray,str.length);
return count;
}
permAlone(‘aab’);