# Finding Permutations of Numbers

I'm trying to solve this challenge, which consists of finding the next biggest number formed by the digits of the passed in number. If it is impossible to find a number larger than the passed in parameter by rearranging the digits, return -1.

EX: nextBigger(12) === 21
nextBigger(2017) === 2071
nextBigger(987654321) === -1


My solution works, but they are testing a bunch of really long numbers that are causing it to time out. I don't even get to see what these really long numbers are because it times out and doesn't return any test cases. I was wondering what could be done to optimize this further.

function nextBigger(n){

let numString = n.toString();
let permutations = []
let smallest = numString[0];
let descending = true;
let same = true;

for(let i = 1; i < numString.length;i++){
if(numString[i-1] < numString[i]){
descending = false;
}
if(numString[i-1] != numString[i]){
same = false;
}

if(smallest > numString[i]){
smallest = numString[i]
}
}
if(descending || same){
return -1;
}

const permute = (prefix, str) => {
let index = String(str).length;
if(index == 1){
permutations.push( prefix + str );
}

for(let i = 0; i < index; i++){
permute(prefix + str[i], str.slice(0,i) + str.slice(i+1,index))
}
}

let nextBiggest = Infinity;
for(let i = numString.length - 2; i >= 0; i--){
let start = numString.slice(0,i);
let end = numString.slice(i,numString.length)
permute(start,end)
for(let j = 0; j < permutations.length; j++){
if(permutations[j] > n && permutations[j] < nextBiggest){
nextBiggest = permutations[j];
}
}
if(smallest == numString[i]){
return nextBiggest
}
permutations = [];
}
return -1
}

console.log(nextBigger(28554))
//42558
console.log(nextBigger(1961821))
//1962118
console.log(nextBigger(12))
//21
console.log(nextBigger(1111))
//-1
console.log(nextBigger(987654321))
//-1

• Make your question self contained regarding the coding problem here, instead of just providing a link please. – πάντα ῥεῖ Jan 10 '17 at 20:20
• I've added the required info. Let me know if I should add anything else. – Tom Pridham Jan 10 '17 at 20:30
• Did you try console.log(nextBigger(1211)) ? – ChatterOne Jan 11 '17 at 11:39
• Just a side note. If they are using V8 to run the code you should avoid using for(let i... as V8 wraps the for loop in a do not optimise flag if you declare a block scoped variable in one of the for statements. Use vars it will improve performance on V8, though for everything but the for loop the improvement is marginal. – Blindman67 Jan 11 '17 at 14:45
• The problem is in your algorithm, need to use a better solution : stackoverflow.com/questions/9368205/… – juvian Jan 11 '17 at 17:56

I'm not entirely sure what this code does, but it certainly seems too long for the problem. First some general review:

      let numString = n.toString();


This is a matter where opinions will certainly differ, but I would prefer to instead assign n = n.toString(); as n is never used again, and the real purpose of this line is to coerce the input to the type which you want to receive.

      let permutations = []


This is a bit surprising: you only need to generate one permutation, so why do you need an array with many? A comment explaining the purpose would be nice.

      let smallest = numString[0];


This is also surprising. "Smallest" in what sense? It's unlikely that the smallest digit will coincidentally be the first one.

      if(descending || same){
return -1;
}


Is there any reason for using two variables here? I think it could be simplified by having one variable which tracks whether there's any increase over the previous digit (although the complete rewrite will eliminate this anyway).

      const permute = (prefix, str) => {


What does this function do? Comment!

        let index = String(str).length;


Earlier the code used toString(); here it uses String(...) to do the same thing. Be consistent.

        if(index == 1){


Although index will always be a number, consistently using === reduces the cognitive load in working out whether == should really have been ===.

      let nextBiggest = Infinity;


WTF? This method was working with strings: where does Infinity come into it?

      return -1


This should be unreachable, so why not throw an exception to alert you to the fact that if it's reached you have a bug?

Now, the part you're really interested in. The algorithm.

The question of finding the next permutation in lexicographic order is a classical one (going back 7 centuries) and well documented in the literature. E.g. Wikipedia gives the following algorithm:

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
• Since you have written an extensive review, you may also want to point out the bug that I talked about in the other comment: console.log(nextBigger(1211)) outputs Infinity instead of 2111. – ChatterOne Jan 11 '17 at 15:54

Javascript is a lot better at handling numbers than strings. Though I am not sure of the range of numbers that the problem will present. If they fall outside the precision of Javascripts double (Number) then you will need to use strings.

If not then the following will improve the performance significantly by working with numbers rather than strings.

function nextBigger(n){
var dig = []; // holds digits lowest first
var pow = []; // holds powers 1,10,100,1000,...
var num = []; // holds dig at power ie dig[i] * pow[i]
var p = 1;  // current power
var nn = n;  // copy of number
var d;       // current digit
var lastD =-1;  // last digit
var i = 0;      // current array index;
var assending = true;  // true if no solution
while(nn> 0){   // get each digit and test for assending
d = nn % 10;  // get the digit
if(d < lastD){  // is it smaller
assending = false
}
pow[i] = p;  // set the power
num[i] = p * d;  // set the dig times power
lastD = dig[i++] = d;  // set the dig in array
nn = Math.floor(nn/10);  // reduce number for next digit
p *= 10;  // get next power
}
if(assending){  // early exit
return -1;
}
if(i === 2){  // quick early exit if 2 digit
return dig[0] * 10 + dig[1];
}
var len = i; // set the length to number of digits found
var cn;  // current number
cn = nn = n;
var np; // Next permutation
var min = Infinity; // current min
var d,p;  // digit and power
var si,sj;  // swap indexes
while(len > 0){
si = -1; // flag no swap
for(i = 0; i < len; i ++){
d = dig[i];  // get digit
p = pow[i];  // and its power
nn = cn - num[i];  // remove it from the current number
for(j = 0; j  < len; j ++){  // for all the othe digits
if(i !== j ){  // not in the same position
// swap the digits
np = nn - num[j] + (pow[j] * d) + (p * dig[j]);
// is the next permutation less than the current min and greater than number
if(np < min && np > n ){
min = np; // set the new min
si = i;   // digits to swap
sj = j;
}
}
}
}
if(si !== -1){ // were digits swapped
var t = dig[si];  // swap the digits in the array
num[si] = (dig[si] = dig[sj]) * pow[si];
num[sj] = (dig[sj] = t) * pow[sj];
cn = min; // set the new value to test
}
len -= 1;
}
return min

}