Finding Permutations of Numbers

Question

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.
• Tom Pridham: I've added the required info. Let me know if I should add anything else.
• ChatterOne: Did you try console.log(nextBigger(1211)) ?
• Blindman67: 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.
• juvian: The problem is in your algorithm, need to use a better solution : stackoverflow.com/questions/9368205/…

Answer 1

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].

• ChatterOne: 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.

Answer 2

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
}