No Repeats Please Help

No Repeats Please Help
0

#1

Hey there, I am working on a challenge and I could use some help with understanding how to use splice inside of a for loop. I was getting an infinite loop, but I seem to have fixed that. Now I am not getting too many potential combinations and I can’t spot the error. My regex test is also not working.

Here are the directions for the challenge:

Return the number of total permutations of the provided string that don’t have repeated consecutive letters. Assume that all characters in the provided string are each unique.

For example, aab should return 2 because it has 6 total permutations (aab, aab, aba, aba, baa, baa), but only 2 of them (aba and aba) don’t have the same letter (in this case a) repeating.

function permAlone(str) {
  var arr = str.split(''),
      newArr = [],
      regex = /(.)\1+/g,
      sliced = [],
      final = [],
      counter = 0;
  
  for (i = 0; i < arr.length; i ++) { 
    var a = arr[i],
        b = '';
    for (j = 0; j < arr.length; j ++) {
      if (i === j) {
        continue;
      } else {
        b += arr[j];
      }
    }
    newArr.push(b);  //newArr contains part of the potential combinations
                     // From here the filtered out character needs to be pushed into
                     // each index position. Ex: newArr[0] = bc. a needs to be pushed in 3 times
                     // to give me abc, bac, bca. This needs to be done for each position in newArr
  }
  
  for (i = 0; i < str.length; i ++) {
    for (j = 0; j <= newArr[i].length; j ++) {
      sliced = newArr[i].split(''); 
      var copy = sliced;
      copy.splice(j,0,str[i]);
      var join = copy.join('');
      final.push(join);         // By this point I have potential combinations, but there are
                                // too many. I should have 6 like the example, but I get 9.
      
    }
  } 
  
  for (i = 0; i < final.length; i ++) {
    if (regex.test(final[i]) === false) {
      counter += 1;
    } 
  }
  return counter; //return final here to test out the total combinations gathered
                  // counter is also not counting the right strings for some reason
  
}

permAlone('aab');


#2

Something to think about - there are n! permutations of a string of size n - and n! = n(n-1)(n-2) ... 1

On the other hand a nested loop over a string of size n is O(n^2) - so there is no way a nested loop by itself can generate all permutations of a string

Working this out on paper for a string of size 4 should uncover the key aspect of the solution

The wikipedia article is hairy but thorough - it has some code too