No Repeats is giving me conniption fits UPDATE: SOLVED. :D **Spoilers**

I tried to do it on my own forever–I even almost had it by just brute force using random numbers but after listening to a Code Newbies podcast where the guest said it was important to be able to recognize when an algorithm is going to be useful, I decided to do it the right way, but I’m just not groking Heap’s algorithm. I’ve been googling and have copy/pasted then played with several of the ones I found, but i still don’t get it to the point that I can really use it in any meaningful way.

Hey @ChadKreutzer there are lots of ways to go about solving this one. For example I used recursion to find all the permutations then a Regular Expression to filter them.

Spoiler alert!!! You can peak at the code [here…](https://www.freecodecamp.com/challenges/no-repeats-please#?solution=%2F*%20Function%20permAlone()%20finds%20all%20possible%20permutations%20of%20the%20user's%20input%2C%20a%20char%20string%2C%20that%20do%20not %20%2F%20%20contain%20repeating%20consecutive%20chars.%20The%20program%20has%20two%20parts.%20The%20first%20part%20finds%20all%20possible %20%2F%20%20permutations%20of%20the%20input%20using%20recursive%20calls%20to%20function%20permute().%20Once%20all%20permutations%20have %20%2F%20%20been%20found%20the%20second%20part%20filters%20out%20any%20permutations%20that%20contain%20repeated%20consecutive%20chars%20by %20%2F%20%20use%20of%20a%20regular%20expression. %20%2F %20%2F%20%20One%20'cycle'%20of%20recursive%20calls%20are%20made%20for%20each%20char%20in%20the%20user's%20input%20string.%20Each%20'cycle'%20fixes%20that %20%2F%20%20char%20as%20the%20last%20character%20for%20each%20permutation%20found.%20Once%20all%20permutations%20are%20found%20a%20new%20cycle%20begins %20%2F%20%20using%20the%20next%20char%20of%20the%20user's%20input%20string.%20Inside%20a%20cycle%20the%20input%20string%20used%20to%20call%20permute() %20%2F%20%20is%20rearranged%20slightly%20to%20find%20the%20different%20permutations.%20*%2F var%20permAlone%20%3D%20function%20(str)%20{ %20%20%20%20function%20permute(inputStr%2C%20removedChars)%20{%20%20%2F%2F%20inner%20function%2C%20permits%20calling%20permAlone()%20with%20single%20argument. %20%20%20%20%20%20%20%20var%20perms%20%3D%20[]%3B %20%20%20%20%20%20%20%20if%20(inputStr.length%20%3D%3D%3D%200)%20{%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20test%20if%20base%20case%2C%20empty%20string%20will%20end%20recursive%20calls. %20%20%20%20%20%20%20%20%20%20%20%20return%20[removedChars]%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20when%20at%20base%20case%20return%20a%20single%20permutation. %20%20%20%20%20%20%20%20}%20else%20{ %20%20%20%20%20%20%20%20%20%20%20%20var%20nextPerm%20%3D%20[]%3B %20%20%20%20%20%20%20%20%20%20%20%20for%20(var%20i%20%3D%200%3B%20i%20<%20inputStr.length%3B%20i%2B%2B)%20{%20%20%20%2F%2F%20iterate%20once%20per%20char%20in%20inputStr. %20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20var%20pre%20%3D%20inputStr.substring(0%2C%20i)%3B%20%20%20%20%20%20%20%2F%2F%20extract%20leading%20i%20chars. %20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20var%20post%20%3D%20inputStr.substring(i%20%2B%201)%3B%20%20%20%20%20%2F%2F%20extract%20remaining%20chars%20less%20the%20first%20i%20%2B%201%20chars. %20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nextPerm%20%3D%20permute(pre%20%2B%20post%2C%20inputStr[i]%20%2B%20removedChars)%3B%20%20%2F%2F%20build%20next%20recursive%20call. %20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20perms%20%3D%20perms.concat(nextPerm)%3B%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20collect%20permutations. %20%20%20%20%20%20%20%20%20%20%20%20} %20%20%20%20%20%20%20%20%20%20%20%20return%20perms%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20return%20permutations. %20%20%20%20%20%20%20%20} %20%20%20%20} %20%20%20%20var%20result%20%3D%20permute(str%2C%20"")%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20find%20all%20permutations%20of%20user%20input%2C%20includes%20repeated%20consecutive%20chars. %20%20%20%20var%20nonRepeatPerms%20%3D%20[]%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20storage%20for%20permutations%20without%20repeated%20consecutive%20chars. %20%20%20%20for%20(var%20j%20%3D%200%3B%20j%20<%20result.length%3B%20j%2B%2B)%20{%20%20%2F%2F%20loop%20over%20all%20permutations%2C%20find%20the%20repeated%20consecutive%20chars. %20%20%20%20%20%20%20%20if%20(!(%2F(.)\1%2F.test(result[j])))%20%7B%20%20%20%20%20%20%2F%2F%20regular%20expression%20tests%20for%20any%20char%20consecutive%20to%20self.%0A%20%20%20%20%20%20%20%20%20%20%20%20nonRepeatPerms.push(result%5Bj%5D)%3B%20%20%20%20%2F%2F%20if%20no%20repeating%20chars%2C%20save%20element%20to%20nonRepeatPerms%20array.%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20nonRepeatPerms.length%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20return%20final%20answer.%0A%7D%3B%0A%0ApermAlone(%27aab%27)%3B%0A)

I get that. I just don’t get it. I’ve been reading all about Heap’s algorithm, but I don’t feel like I really understand it.

Recursion IS twisted and difficult to wrap your head around. Simple recursion everyone gets, but when each iteration is doing something tricky it quickly gets more difficult to conceptualize what the heck is going on. Sometimes writing a few iterations out on paper helps. Also have a look at the code I posted above, it is well commented.

1 Like

I tried to. when I clicked the link the code box was empty.

Sorry about that - I’m not sure why that’s happening, but here it is below…

okay. I was able to figure it out non-recursively by examining the graphic at the wikipedia page (I think anyhow, at least it looks right so far):

console.log(perm('aab'))

function perm(str) {
  var arr = str.split('')
  var permList = []
  var n = arr.length
  for (var i = 0; i < n; i++) {
    for (var j = 1; j < n - 1; j++) {
      permList.push(swap(arr, 0, j).join(''))
    }
    permList.push(swap(arr, 0, n - 1).join(''))
  }
  return permList
}

function swap(a, p1, p2) {
  var temp
  temp = a[p1]
  a[p1] = a[p2]
  a[p2] = temp
  return a
}

now to see if I can make it recursive.

edit: Hmm. I tried plugging it into the problem to see how it was going so far and it didn’t seem to work for the bigger ones: it says 42 instead of a number in the thousands. I’m missing something… I think it might be another loop.

I have resolved this one recently and was a big pain, I made a tree with all the possibilities who has every branch to get the permutations.

@Luiko @rickstewart

Well, I think I got it working for reals:

var permutation = []
perm(['a','b','c','d'])
console.log(permutation)


function perm(arr, n){
  n = n||arr.length
	if(n === 1) permutation.push(arr.join(''))
	else{
		for(var i = 0; i < n - 1; i++){
			perm(arr, n - 1)
			if(n % 2) arr = swap(arr, 0, n - 1)
        else arr = swap(arr, i, n - 1)
		}
  perm(arr, n - 1)
	}
}

function swap(a, p1, p2){
  var temp = a[p1]
  a[p1] = a[p2]
  a[p2] = temp
  return a
}

Granted, it was javascriptization of the pseudo code example at the wikipedia page with a little bit of tweaking. But I had tried it before and it didn’t work. I’m gonna do some tracing of variables as it works tonight at work to try to understand it better, but I feel good enough about this to go ahead and finish the challenge. (the regex part was easy.)

I’m gonna look into closures too, cause if I understand it correctly, that is how I would be able to not have permutation as a global.

Aaannnd solved it:

function permAlone(str) {
  var permutation = [];
  var strArr = str.split('');
  return perm(strArr);

  function perm(arr, n) {
    n = n || arr.length;
    if (n === 1) {
      var arrStr = arr.join('');
      if (arrStr.search(/(.)\1/) === -1) permutation.push(arrStr);
    } else {
      for (var i = 0; i < n - 1; i++) {
        perm(arr, n - 1);
        if (n % 2) arr = swap(arr, 0, n - 1);
        else arr = swap(arr, i, n - 1);
      }
      perm(arr, n - 1);
    }
    if (n === arr.length) return permutation.length;
  }

  function swap(a, p1, p2) {
    var temp = a[p1];
    a[p1] = a[p2];
    a[p2] = temp;
    return a;
  }

}

Now all I have left is twitch, tic tac toe, and simon!

1 Like

Hey Chad, there is simple solution to this. Wrap your code in a immediately-invoked function expression (or IIFE, pronounced “iffy”). This not only cleans up the Global address space but makes your code private. Then using a return statement in a very particular way you can make public only the functions you want to expose. This is the “Module” pattern.

See the code here.

An example::

The IIFE pattern is awesome not just for elegance, but for security as well. Aside from bugs in the JS engine itself, nothing can get at privateMethod from the outside. In the world of client-side JS where browsers routinely load third-party code on a whim, that can poke around and mess with other JS at will, encapsulation===security.

Might want to be careful about the term “Module” though: ES6 has modules now, they’re implemented differently, and while I think the IFFE pattern is superior, the confusion over an overloaded term is only going to mount over time.

There term Module was taken directly from here:

I cannot say how official it is though…

1 Like

From what I can tell, ES6 modules were in fact based on that pattern (I wasn’t there, I wouldn’t know). Stuff like webpack implements modules as functions (there’s not much else they can use), so they share common DNA. I just say “IIFE” these days and leave the word “module” to the hash the standards committee made of it :stuck_out_tongue_winking_eye:

I tried doing this, and my solution works, except that I get a ‘RangeError: Maximum call stack size exceeded’ for inputs that are more than 6 characters. How did you get around that limitation?

1. When you are forming each permutation, and you come across one that has repeating letters, you do not need to keep going.

this is the difference between only going through a handful of steps to solve the test case ‘aaaaaaaa’, or finding 40320 permutations just to filter every single one out afterwards.

2. You are asked to return a number, not a list. Storing an array of thousands of strings is unnecessary.

You dont actually need the list of strings, you just need to keep track of how many you find. This is only possible when you keep (1) in mind.

You can think of the problem in this way:

How many unique routes can I take through a string, without passing through identical letters consecutively?

Then you can set up a much simpler algorithm to traverse the letters of a string and count how many times it can successfully get through the entire string without hitting the same letter twice.

This is one possible solution using these two ideas:

function permAlone(s,p){

  return s.split('').reduce(
    (x,y,i)=> y==p ? x : s.length==1? 1 : x + permAlone(s.slice(0,i) + s.slice(i+1),y) ,0);
  
}

I dint’t read your solution but I also used recursion to find the permutations and regular expression to filter. The problem is, it works for small strings but, for example, for ‘aaaaak’ it get stuck. Is there a possibility that the code is very inefficient or it is wrong? My solution…

I saw what my problem was.

Hi, I’m really trying to understand Recursions… it’s really hard and frustrationg… The basic function for factorials is easy to understand but for no Repeats… I just can’t seem to rap my head around how recursion works…

I’ve actually gotten all greens with the problem but I haven’t submitted it. My code is a snippet Frankenstein from various stackoverflow code which I don’t completely understand and I was hoping to really understand recursion before I move on.

I’m trying to understand the code you pasted as a jpeg in relation to this one which I got from the chat forums:


from: Ghulam Shabir @ghulamshabir at the chat rooms for javascript

function generate(n, arr) {
        if (n === 1) {
            console.log(arr);
            return;
        }


        for( var i = 0; i < n; i + + ) {
             generate (n - 1, arr);

            if( n % 2 === 0 )
                swap(arr, i,  n - 1);
            else
                swap(arr, 0, n - 1);
    }
}            
            function swap(arr, idxA, idxB) {
        var temp = arr[idxA];
        arr[idxA] = arr[idxB];
        arr[idxB] = temp;
    }

They seem similar to me and both seem to use heap’s method as Ghulam Shabir @ghulamshabir suggested I study in producing the original permutations… The filtering I also found on the chat forums. My main concern is understanding just the block of code that produces the permutations…

I understand heap’s method is the following:

Given N is the total number of elements in an array ARR and a counter i which counts until N:
Get all the permutations of the first N-1 elements and then just add the last element of ARR to these for the first iteration of the counter ‘i’. as i counts up… depending on whether the N elements is odd or even, switch the last element of ARR with either the ‘i’ element or the first element.

I get the switch part of the code for switching the first, last and i elements after every succession of I. What I don’t get is where in the code the permutations of the first N-1 elements are generated? Does anybody know a step-by-step walkthrough for the code itself? there are numerous diagrams on the net but I haven’t found one that explains how the “computer” applies these “plans” in recursion. Thanks again… hope to figure it out before I move on… Thanks.