Hey guys,
I started the “No Repeats Please” challenge and i’m seriously lost, i’ve read the guide, i still don’t understand what i have to do, how the Heap’s algorithm works and i have any idea on how to even approach the problem.
Am I just stupid or is the challenge really, really hard?
Sorry I don’t have time to give a detailed answer (off to work) but I just wanted to pipe in and say that you are not stupid because of having difficulty with this challenge. I consider myself pretty good at algorithms and this one knocked me on my but for a while.
One way to approach it would be to break it into pieces. First you have to generate and array of permutations, then count how many don’t have repeats.
Do you understand permutations? Do some research. See if you can figure out how to make permutations. I used recursion in mine, but I’m sure there are other solutions.
I’ll basically just repeat @ksjazzguitar - this is hard. Heap’s algorithm is not intuitive at all, so it can take some time to wrap your noodle around it. In general, don’t be discouraged when you come to something you don’t understand. Learn to breathe and work through the feeling of being lost. It’s going to happen a lot more from here on out.
I just came across this great primer on permutations and combinations that you might find useful
I’m curious why many posts on this forum mention Heap’s algorithm for permutations for the “No repeats” problem - is it recommended in some solution for the problem or does it show up high in a google search?
Both, if i recall correctly. Heap’s is pretty much the canonical permutation algorithm, so it makes sense edit: maybe I shouldn’t be typing after I’ve had wine.
How is Heap’s the “canonical” permutation algorithm?
I don’t want to exaggerate on account of my dinner wine. I just mean that in discussions and lectures on algorithms, I frequently see Heap’s when we come to permutations.
First things first, of course not, the challenges are difficult - they are designed to teach you problem solving skills and to make sure you go back and learn the concepts you don’t fully understand. I’m just getting started with the intermediate algos - remember it’ll be hard but your problem solving skills develop and you become a better developer.
The fact you are on advanced algos shows that you have already learned a lot. Make sure you keep reading through all of the provided information for the challenge - be sure to read up on all the needed methods on MDN - and keep working towards it - you’ll find a solution in no time 
Fair enough - I do see google “permutations algorithm” returns pages for Heap’s algorithm as the second and third hits - the top hit is a stackoverflow post that actually describes an obvious and simple algorithm - it does not have code - maybe that makes people look more to Heap’s for implementation - this is unfortunate for someone solving permutations for the first time - Heap’s was discovered in 1963 while permutation algorithms have been known for hundreds of years - even then Heap’s was not appreciated till Sedgwick pointed out its efficiency - this suggests Heap’s is not among the more obvious algorithms even to experts in the field
I recommend systematically writing out permutations on paper for strings of length 3 and 4, say “abc” and “abcd”, and discovering simpler recursive and iterative solutions to the problem before trying Heap’s
So this is what i’ve got so far:
(spoilers, obviously)
function permAlone(str) {
var arr = str.split('');
var perms = [];
permutation(arr, arr.length, perms);
var result = checkRepeating(perms);
return result;
}
var swap = function(array, pos1, pos2) {
var tmp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = tmp;
};
var permutation = function(array, n, output) {
if(n === 1) {
output.push(array);
} else {
for(var i = 0; i < n - 1; i++) {
permutation(array, n - 1, output);
n % 2 ? swap(array, i, n - 1) : swap(array, 0, n - 1);
}
permutation(array, n - 1, output);
}
return output;
};
var checkRepeating = function(array) {
var regex = /(.)\1/;
var counter = 0;
array.forEach(function(el) {
var str = el.join('');
if (!str.match(regex)) counter++;
});
return counter;
};
permAlone("aab");
Problem is that the perms variable is an array of the same exact permutation.
The function permutation returns a value, which is probably the array of arrays that you’re expecting.
It does return the array of arrays, but with the same value every time.
Ex:
[ [a, a, b], [a, a, b], [a, a, b] ]The bug is very subtle. n % 2 is falsey if n is even, so you need to switch your calls to swap around. This should get you all of the permutations, but there will be another problem to solve after that.
Yep, the problem with the perms variable is still there, i think it has something to do with the scoping, but i can’t quite grasp what.
Alright, I’ve got it for reals this time. I’m not sure why this is the case just yet (which is bugging me to no end), but we can make just two, simple change from your original code:
if (n === 1) {
output.push(array.join(''));
}
//later
array.forEach(function(el) {
// remove the join() call here
if (!el.match(regex)) counter++;
});
I agree that this seems to be a scoping issue, but I don’t have an answer as to why your code didn’t work.
Full code:
function permAlone(str) {
var arr = str.split('');
var perms = [];
permutation(arr, arr.length, perms);
var result = checkRepeating(perms);
return result;
}
var swap = function(array, pos1, pos2) {
var tmp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = tmp;
};
var permutation = function(array, n, output) {
if (n === 1) {
output.push(array.join(''));
} else {
for (var i = 0; i < n - 1; i++) {
permutation(array, n - 1, output);
n % 2 ? swap(array, 0, n - 1) : swap(array, i, n - 1);
}
permutation(array, n - 1, output);
}
};
var checkRepeating = function(array) {
var regex = /(.)\1/;
var counter = 0;
array.forEach(function(el) {
if (!el.match(regex)) counter++;
});
return counter;
};
permAlone("aab");
Wow, thanks for the help.
Is this one of those times you just go: “It works, i don’t know why or how but it does”?