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

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

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

}