"No Repeats Please" Challenge Help!

"No Repeats Please" Challenge Help!
0

#1

I have come up with the following code for this challenge. The problem is it works with some cases while not with some other! And I can’t seem to get why it’s not working there. So can somebody look into it?

PS:

  • It works with permAlone("aab"), permAlone("aaa"), permAlone("aabb"), permAlone("zzzzzzzz"), permAlone("aaab"), permAlone("a")

  • It doesn’t work with permAlone("aaabb"), permAlone("abcdefa"), permAlone("abfdefa")

  • console.log statements will help you to follow the flow of the program.

 function swap(arr, x, y) {
  var temp = arr[x];
  arr[x] = arr[y];
  arr[y] = temp;
  return arr;
}

function factorial(n) {
  var facto = 1;
  for (var k = 1; k <= n; k++) {
    facto = facto * k;
  }
  return facto;
}

function permAlone(str) {
  var charArr = str.split("");
  console.log(charArr);
  var n = charArr.length;
  var f = factorial(n);
  console.log("f="+f);
  var permArr = [];
  if(n == 1) {
    return 1;
  } else {
    for (var i = 0; i < f/(n-1); i++) {
      for (var j = 0; j < n-1; j++) {
        charArr = swap(charArr, j, j+1);
        //console.log(charArr);
        //permArr.push(charArr);
        permArr +=  charArr + ";" ;
        permArr = permArr.replace(/,/g,'');
        console.log(permArr);
      }
    }
    permArr = permArr.slice(0,-1).split(";");
    console.log(permArr);
  
    var count = 0;
    for (var m=0; m < permArr.length; m++) {
      if(/([a-z])\1{1,}/.test(permArr[m]) === false) {
        count++;
      }
    }
    return count;
  }
}

permAlone('aaabb');

#2

I think there’s something wrong with your permutation generator. If you tried 'aaabb', it should produce these 10 (unique) permutations:

aaabb    aabab
abaab    baaab
aabba    ababa
baaba    abbaa
babaa    bbaaa

5! = 120, so there must be 12 versions of each permutation. When I printed your array of permutations, I noticed that aaabb has 24 versions, aabab has 12, and so on. Specifically, the permutation that we want, ababa has only 6 versions, not 12. (it’s easier to see if you sorted the array before printing)


#3

Thanx for the reply! What bewilders me is that it works up to 4 chars, then suddenly stops working. But you have given me the direction & I will look into it more closely.


#4

The problem
Your permutation generator. You only switch between 2 items that are next to each other, so some permutation will never be generated. For example, from the string “1234” your generator can produce these strings:
2134
2314
2341
3241
3421
3412
4312
4132
4123
1423
1243
1234
After 4 times j variable running from 0 to 2 (after i is increased by 4), it comes back to “1234”, and in the next loops it will produce what have appeared before. So in this case you generator can produce only 12 unique permutation, while it should produce 24.


Permutation generator algorithm
You can figure out a better generator by trying with an example. With that string “1234”, the next bigger numbers you can have by permutating digits are:
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
And so on… until it reaches 4321
When you permutate in this order, you can be sure that you don’t miss any possibility.
So can you find out the rule of that list?