I had completed this challenge yesterday and now I want to share my solution. My code is not short and it takes about 20 seconds to pass the tests, but on the positive side it’s quite easy to understand its logic.
I tried to make the description of my method as full as possible, so read it carefully if you still haven’t completed this challenge. I also attached my code under the spoiler at the end.
So at first I tried to figure out or google for a formula of calculating number of permutations, but failed. OK, I thought, then I need to generate them. But how? No idea. OK, let’s generate combinations and then somehow filter permutations out of them. But I still had no idea how to do it.
And then I imagined a safe, which has digits from 0 to 9 on its buttons and a 10-digit combination to open it. The number of possible combinations is easy to calculate – just raise number of buttons to the power of combination lengts: 10^10 = 10.000.000.000. Then if we want to generate all the combinations, it will start from all zeros and end with all nines. So basically we start from zero, increment it by one each time and add some zeros to the left side to make required length of combination.
0000000000
0000000001
0000000002
…
9999999999
At this point it started looking familiar to me. And I had added some square brackets:
[0][1][2][3][4][5][6][7][8][9]
Aren’t these indicies? Let’s add some letters.
string: a b c d e f g h i j
index: [0][1][2][3][4][5][6][7][8][9]
[0][0][0][0][0][0][0][0][0][0]
a a a a a a a a a a
[0][0][0][0][0][0][0][0][0][1]
a a a a a a a a a b
[0][0][0][0][0][0][0][0][0][2]
a a a a a a a a a c
Yay! It works! But what if we have combination of not 10, but say 4 characters (0123)?
0000
0001
0002
0003
We don’t have a 4 in our arsenal, so the we should increment previous symbol, and the next values will be:
0010
0011
0012
0013
0020
0021
Doesn’t it look familiar again? It’s still our indicies, but it’s also a quaternary numeral system. And if we had a string of two characters (like “ab”), that would be a binary numeral system.
Now we need to somehow convert out habitual decimal system to whatever system we need (based on a length of input string). If you google for it, you’ll easily find out that it’s not a problem at all. Let’s say you need to convert number 26 to quaternary system.
Divide 26 by the 4 (4 represents quaternary system):
26 / 4 = 6 (whole number) and reimainder is 2. Divide your result by 4 again:
6 / 4 = 1 (whole number) and remainder is 2. Divide last time and you’ll get remainder = 1. Then put all of remainders together and you’ll get 221. The picture below may help to understand it better:
Now we need to look at our result from right to left, or in another words – reverse it: 221 --> 122. That’s our final result, 27 in decimal system will be 221 in quaternary system. Remember, that out string length is 4, so we need to add one zero to the left: 0221. Now that’s your indicies. And if your string at input was “abcd”, then 27-th combination will be “accb”:
a b c d
[0][1][2][3]
[0][2][2][1]
a c c b
So the whole algorithm for our function will be:
- Generate regular numbers starting from zero (which is just increment function);
- Convert our number to a numeral system we need (which is our input string’s length);
- Add zeros to the left until we get proper length (which is also our input string’s length);
- Split numbers we’ve got to make an array, which elements will serve as indicies for our string. At this point I also use a check for repeated consecutive indicies, cause they will make repeated consecutive letters.
- Use indicies we’ve got to generate an array of letters out of our string. Check for repeated consecutive letters. If they are – go to step #1 and generate our next number, if they aren’t – increase our permutations counter, then go to step #1 and generate our next number.
And we do it until we reach maximum number of possible combinations which is calculated as x^x, where x is our string’s length.
My code is here
// noprotect
function convNumSys(val, sys) {
var newNum = [];
if (val === 0) {
return false;
}
while (val > 0) {
newNum.push(val % sys);
val = (val - val % sys) / sys;
}
newNum = newNum.reverse();
while (newNum.length < sys) {
newNum.unshift(0);
}
var repeated = isRepeatNumber(newNum);
if (repeated === true) {
return false;
} else {
return newNum;
}
}
function isRepeatNumber(arr) {
for (var b = 0; b < arr.length - 1; b++) {
if (arr.join("").split(arr[b]).length > 2) {
return true;
}
}
return false;
}
function isRepeatLetter(arr) {
for (var a = 0; a < arr.length - 1; a++) {
if (arr[a] === arr[a + 1]) {
return true;
}
}
return false;
}
function permAlone(str) {
var totalCycles = Math.pow(str.length, str.length);
var currentCycle = 0;
var permCounter = 0;
if (str.length === 1) { //special case
return 1;
}
while (currentCycle < totalCycles) {
var indexes = convNumSys(currentCycle, str.length);
if (indexes === false) {
currentCycle += 1;
} else {
var lettersArr = [];
for (var b = 0; b < indexes.length; b++) {
lettersArr.push(str[indexes[b]]);
}
if ( isRepeatLetter(lettersArr)) {
currentCycle += 1;
} else {
currentCycle += 1;
permCounter += 1;
}
}
}
return permCounter;
}
permAlone('abfdefa');