No repeats please. This is a tough one, really. We are going to bruteforce this challenge instead of using clever mathematics this time around. Simply because it will let us do a few more things.
This bonfire will have us write a function that, given a string as argument, returns the number of permutations with no repeated consecutive characters. A permutation is simply an arrangement items in a specific order; in today’s context, we could say that a permutation is nothing but an arrangement of letters within a string.
Let’s see some examples for permutations of the string ‘aabs’. Remember that permutations that contain repeated consecutive characters should not be counted:
- aabs – Invalid, consecutive a’s
- abas – Valid
- baas – Invalid, consecutive a’s
- absa – Valid
As you can see, those strings with repeated a‘s should not be counted. Another important thing to have in mind for this particular exercise, is that each letter (even if repeated) is a unique instance or item within the permutation. In other words, in the string ‘aab’, the ‘a’ characters can be interchanged to form these permutations:
aab 12 aab 21 aba 1 2 aba 2 1 baa 12 baa 21
We need to count each ‘a’ as if it were a unique character. I used the numbers 1 and 2 under the a‘s to distinguish them.
Let’s get started. The way in which we are going to find the solution looks pretty simple (although not so easy to achieve!):
- Generate every permutation of the input string. (We’ll use Heap’s algorithm)
- Remove those with repeated characters. (Using regular expressions)
- Return the number of permutations left.
First of all, we’ll going to create a JavaScript implementation of Heap’s algorithm:
function heap(string) {
var arr = string.split(''), // Turns the input string into a letter array.
permutations = []; // We'll store the results here.
function swap(a, b) { // This function will simply swap positions a and b inside the input array.
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
function gen(n) { // This is the big guy in the block. I could go on and on about
if (n === 1) { // what it is that it does exactly, but you're better off going
permutations.push(arr.join('')); // to Wikipedia and reading on Heap's Algorithm
} else {
for (var i = 0; i != n; i++) {
gen(n - 1);
swap(n % 2 ? 0 : i, n - 1);
}
}
}
gen(arr.length);
return permutations;
}
[ecko_contrast]
Heap’s Algorithm Execution
The logic inside this particular function is quite abstract, as is usually the case with recursive functions (functions that call themselves).
In an attempt to make this easier to grasp, here’s a walk-through of a single execution of the heap() function for the string ‘hey’.
heap('hey')
--------------------------------
arr = ['h', 'e', 'y'];
permutations = [];
gen(3) | n = 3
n === 1 is false
while i is not equal to 3, loop and increment i on each loop
--loop | i = 0
Execute: gen(3 - 1) | n = 2
n === 1 is false
while i is not equal to 2, loop and increment i on each loop
loop | i = 0
Execute: gen(2 - 1) | n = 1
n === 1 is true so we join the contents of arr and add it to permutations:
permutations = ['hey'];
Execute: swap(0, 1) -> Swaps array positions 0 and 1 -> arr = ['e', 'h', 'y']
loop | i = 1
Execute: gen(2 - 1) | n = 1
n === 1 is true, so we join and add as before:
permutations = ['hey', 'ehy'];
Execute: swap(1, 1) -> Swaps array positions 1 and 1 -> arr = ['e', 'h', 'y']
|| STOP LOOP, as i = 2 and n = 2 | gen(3 - 1) is done
Execute: swap(0, 2) -> Swaps array positions 0 and 2 -> arr = ['y', 'h', 'e']
--loop | i = 1
Execute: gen(3 - 1) | n = 2
n === 1 is false
while i is not equal to 2, loop and increment i on each loop
loop | i = 0
Execute: gen(2 - 1) | n = 1
n === 1 is true, so we join and add as before:
permutations = ['hey', 'ehy', 'yhe'];
Execute: swap(0, 1) -> arr = ['h', 'y', 'e']
loop | i = 1
Execute: gen(2 - 1) | n = 1
n === 1 is true, so we join and add as before:
permutations = ['hey', 'ehy', 'yhe', 'hye'];
Execute: swap(1, 1) -> arr = ['h', 'y', 'e']
|| STOP LOOP, i = 2
Execute: swap(0, 2) -> Swaps array positions 0 and 2 -> arr = ['e', 'y', 'h']
--loop | i = 2
Execute: gen(3 - 1) | n = 2
n === 1 is false
while i is not equal to 2, loop and increment i on each loop
loop | i = 0
Execute: gen(2 - 1) | n = 1
n === 1 is true, so we join and add as before:
permutations = ['hey', 'ehy', 'yhe', 'hye', 'eyh'];
Execute: swap(0, 1) -> arr = ['y', 'e', 'h']
loop | i = 1
Execute: gen(2 - 1) | n = 1
n === 1 is true, so we join and add as before:
permutations = ['hey', 'ehy', 'yhe', 'hye', 'eyh', 'yeh'];
Execute: swap(1, 1) -> arr = ['y', 'e', 'h']
|| STOP LOOP, i = 2
Execute: swap(0, 2) -> Swaps array positions 0 and 2 -> arr = ['h', 'e', 'y']
|| STOP LOOP, i = 3
return permutations variable = ['hey', 'ehy', 'yhe', 'hye', 'eyh', 'yeh'];
Another way to easier understand what’s going on inside, it to add some log messages. I’ve updated my heap function to look like so:
function heap(string) {
var arr = string.split(''),
permutations = [];
function swap(a, b) {
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
function gen(n) {
if (n === 1) {
permutations.push(arr.join(''));
console.log('Added: ' + arr.join(''));
} else {
for (var i = 0; i != n; i++) {
gen(n - 1);
console.log('Swap: ' + (n % 2 ? 0 : i) + ' and ' + (n - 1));
console.log('Original: ' + arr);
swap(n % 2 ? 0 : i, n - 1);
console.log('Swapped: ' + arr);
console.log('----------------');
}
}
}
gen(arr.length);
return permutations;
}
Execute it yourself and you’ll be able to see what happens as we go.
[/ecko_contrast]
Okay, cool. We can generate permutations out of thin air, a string and a function. They are stored in the return value, permutations. Now, we need to filter out those with consecutive repeated characters. This screams of RegEx, so let’s do that.
We are going to be using capturing groups and backreferences. A backreference is a reference *duh* to a previously defined capturing group, that’s why we call them back-references. The are written like so x where x is the index for a specific capturing group. Let’s see it in action:
var regexOne = /(hello)1/; //-> Will match 'hellohello', 1 is equal to the first capturing group. var regexTwo = /(hi) (there) : 2 1/; //-> Will match 'hi there : there hi', 1 is equal to 'hi' and 2 is equal to 'there' var regexThree = /(d.g)1/; // Matches dogdog, dagdag etc. but will NOT match dogdag or dugdog for instance.
Let’s use this knowledge to our advantage. We want to match repeated consecutive characters. A single character is represented as a dot “.” in RegEx; let’s use a capturing group, a dot and a backreference all together:
var consecutive = /(.)1/; // Will match any consecutive repeated characters.
Simple enough! We don’t need to get complex here, even if we get three or four consecutive characters, just two is enough to discard the permutation, and that’s what this RegEx will match.
Now that we have an array of permutations and a regular expression that detects those with repeated characters, let’s filter them out with… Yes! Filter!
function permAlone(string) {
var consecutive = /(.)1/;
return heap(string).filter(function(currentPerm) { // We filter out items that match the regex.
return !consecutive.test(currentPerm); // Notice the ! in from of the test, we only want those results that DON'T match.
});
// Our lovely implementation of Heap's algorithm.
function heap(string) {
var arr = string.split(''),
permutations = [];
function swap(a, b) {
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
function gen(n) {
if (n === 1) {
permutations.push(arr.join(''));
} else {
for (var i = 0; i != n; i++) {
gen(n - 1);
swap(n % 2 ? 0 : i, n - 1);
}
}
}
gen(arr.length);
return permutations;
}
}
Okay, we are now returning an array of permutations with no repeated characters. But we need to return a number, not the whole thing. A single word should take care of that:
function permAlone(string) {
var consecutive = /(.)1/;
return heap(string).filter(function(currentPerm) {
return !consecutive.test(currentPerm);
}).length; // We return the length of the filtered array.
function heap(string) {
var arr = string.split(''),
permutations = [];
function swap(a, b) {
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
function gen(n) {
if (n === 1) {
permutations.push(arr.join(''));
} else {
for (var i = 0; i != n; i++) {
gen(n - 1);
swap(n % 2 ? 0 : i, n - 1);
}
}
}
gen(arr.length);
return permutations;
}
}
All set. We are now ready to get onto the last challenge. Stay tuned, we are almost there!
As always, feel free to shoot me an email, ping me on twitter or post a comment below if anything is unclear or you’ve got any questions .
StartJS 