Permutations filtered with no repeating characters

Question

This is a task from freeCodeCamp.

My goal is to create a function which:

1. Takes any string with any characters.
2. Creates an array with all the permutations possible out of that string.
3. Filters the array and returns only the strings which don't have repeated consecutive letters.

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.

I can't figure out what have i wrote wrong. I think the problem lies either in the filter function or the permutation list is faulty.

function permAlone(str) {

    if (str.length == 1) {
        return str;
    }
    // Creates all possible Permutations and pushes to an array 
    var arr = [];
    var p = 0; // position of the element which needs to be swapped
    // Loop count equal to number of Permutations.
    var loops = factorialize(str.length);
    for (var i = 0; i < loops; i++) {

        // if the position is not the last element in the strig keep swapping with next following character

        if (p != str.length - 1) {
            var splitStr = str.split('')
            arraySwapElements(splitStr, p, p + 1);
            str = splitStr.join('');
            arr.push(str);
            p += 1;
            // when position is at the last index, change position to 0
        } else {
            p = 0;
            i -= 1;
        }
    }

    // swaps 2 items in an array

    function arraySwapElements(arr, a, b) {
        var item = arr[a];
        arr[a] = arr[b];
        arr[b] = item;
    };


    // outputs a factorial of a number

    function factorialize(num) {
        if (num === 0) {
            return 1;
        } else {
            return num * factorialize(num - 1);
        }
    }

    // filters any array which has 2 or more repeating characters

    var x = arr.filter(function(str) {
        var re = /(.)\1+/;
        var result = re.test(str);
        if (!result) {
            return str;
        }
    })

    // returns the filtered arrays length
    return x.length



}

console.log(permAlone('abfdefa'));

When testing:

permAlone("aab") should return a number. // Correct
permAlone("aab") should return 2.  // Correct
permAlone("aaa") should return 0. // Correct
permAlone("aabb") should return 8. // Correct
permAlone("zzzzzzzz") should return 0.// Correct
permAlone("a") should return 1.// Correct
permAlone("aaab") should return 0.// Correct

permAlone("abcdefa") should return 3600. // Incorrect
permAlone("abfdefa") should return 2640.// Incorrect
permAlone("aaabb") should return 12. // Incorrect

Answer 1

The issue stems from the logic used in the for loop. While the loop does generate the right number of total permutations, it doesn't generate all permutations.

For example, if our string to be permuted was "abcd", the swapping mechanism would generate strings like this:

bacd bcad bcda

cbda cdba cdab

dcab dacb dabc

adbc abdc abcd

Uh oh! That last arrangement is the same as the starting string. When we start swapping again, we're going to get the same set that we did on the first pass. We're never going to get a permutation like "acbd". Thus the resulting array contains higher numbers of some permutations and lower numbers of others.

I'm not sure how to fix it with the approach you're using, but a recursive function to get permutations could be written like this:

// Returns an array of all permutations of a string
function getPerms(str) {
  // Base case. If the string has only one element, it has only one permutation.
  if (str.length == 1) {
    return [str];
  }
  // Initialise array for storing permutations
  let permutations = [];
  // We want to find the permutations starting with each character of the string
  for (let i = 0; i < str.length; i++) {
    // Split the string to an array
    let splitStr = str.split('');
    // Pull out the character we're checking for permutations starting with
    let currentElem = splitStr.splice(i, 1)[0];
    // Get permutations of the remaining characters
    let subPerms = getPerms(splitStr.join(''));
    // Concat each of these permutations with the character we're checking
    // Add them to our list
    subPerms.forEach(function (combination) {
      permutations.push(currentElem.concat(combination));
    });
  }
  // return our list
  return combinations;
}