问题描述:

I'm currently working on coderbyte's medium challenge entitled "Permutation Step."

The goal is to take user input, num, and to return the next number greater than num using the same digits So, for example, if user input is 123, then the number 132 should be returned. If user input is 12453, then 12534 should be returned...

Anywho, I have a correct model answer created by someone (probably a genius, cuz this stuff is pretty hard) and I'm trying to figure out how the answer works, line for line by having an example play out (I'm keeping it simple and playing out the function with user input 123).

The answer has 2 functions, but the 1st function used is what I'm currently trying to work out...

The relevant code is:

var PermutationStep1 = function(num) {

var num1 = num.toString();

var ar = [];

//return num1;

if (num1.length < 2) {

return num;

} else {

for(var i = 0; i < num1.length; i++) {

var num2 = num1[i];

var num3 = num1.substr(0,i) + num1.substr(i+1, num1.length -1);

var numAr = PermutationStep1(num3);

for(var j = 0; j < numAr.length; j++) {

ar.push(numAr[j] + num2);

}

}

ar.sort(function(a,b) {return a-b});

return ar;

}

}

Again, I'm trying to work thru this function with the inputted num as 123 (num = 123).

I'm pretty sure that this function should output an array with multiple elements, because the 2nd function merely compares those array elements with the original user input (in our case, 123), and returns the next greatest value.

So in our case, we should probably get an array, named 'ar', returned with a host of 3 digit values. But for some reason, I'm getting an array of 2 digit values. I can't seem to isolate my mistake and where I'm going wrong. Any help with where, specifically, I'm going wrong (whether it be the recursion, the use of substring-method, or the concating of strings together, whatever my problem may be) would be appreciated...

Here's some of my work so far:

PS1(123) / num1 = 123

i = 0;

num2 = (num1[i]) = '1';

num3 = (num1.substr(0, 0) + num1.substr(1, 2)) = ('0' + '23') = '23'

PS1(23)

i = 0;

num2 = '2';

num3 = '3'

PS1(3) -> numAr = 3 (since num1 is less than 2 digits, which is the recursion base case?)

(So take 3 into the 2nd for loop)...

ar.push(numAr[j] + num2) = ar.push('3' + '1') = 31

ar = [31] at this point

And then I go through the initial for-loop a couple more times, where i = 1 and then i = 2, and I eventually get....

ar = [31, 32, 33]...

But I'm thinking I should have something like ar = [131, 132, 133]? I'm not sure where I'm going wrong so please help. Because the answer is correctly spit out by this function, the correct answer being 132.

Note: if you need the 2nd part of the model answer (i.e. the 2nd function), here it is:

var arr = [];

function PermutationStep(num1) {

arr.push(PermutationStep1(num1));

var arrStr = arr.toString();

var arrStrSpl = arrStr.split(",");

//return arrStrSpl;

for(var p = 0; p < arrStrSpl.length; p++) {

if(arrStrSpl[p] > num1) {

return arrStrSpl[p];

}

}

return -1;

}

网友答案:

I'm sorry the first function i posted was under a mathematical logical mistake and i was to overhasty I thought about it again and now i have the following function which definitley works

function getNextNumber (num)
    {
    var numberStr=num.toString (), l=numberStr.length, i;

    var digits=new Array (), lighterDigits, digitAtWeight;
    var weight,lightWeight, lighterDigits_l, value=0;

    for (i=l-1;i>-1;i--)
        digits.push (parseInt(numberStr.charAt(i))); 

    lighterDigits=new Array ();
    lighterDigits.push (digits[0]);

    for (weight=1;weight<l;weight++)
        {
        digitAtWeight=digits[weight];
        lighterDigits_l=lighterDigits.length;


        for (lightWeight=0;lightWeight<lighterDigits_l;lightWeight++)
            {
            if (digitAtWeight<lighterDigits[lightWeight])
                {

                lighterDigits.unshift (lighterDigits.splice (lightWeight,1,digitAtWeight)[0]);
                lighterDigits.reverse ();
                digits=lighterDigits.concat (digits.slice (weight+1,l));
                for (weight=0;weight>l;weight++)
                    value+=Math.pow (10,weight)*digits[weight];
                return value;
                }
            }
        lighterDigits.push (digitAtWeight);
        }       
    return NaN;
    }
网友答案:

okay here is my solution i found it in 20 minutes ;)

//---- num should be a Number Object and not a String
function getNextNumber (num)
    {
    var numberStr=num.toString (), l=numberStr.length, i;
    var digits=new Array (), digitA, digitB;
    var weight,lightWeight;
    var valueDifference,biggerValue;

    for (i=l-1;i>-1;i--)
        digits.push (parseInt(numberStr.charAt(i)));   //  345 becomes a0=5 a1=4 a2=3 and we can say that num= a0*10^0+ a1*10^1+ a2*10^2, so the index becomes the decimal weight

    for (weight=1;weight<l;weight++)
        {
        digitA=digits[weight];
        biggerValue=new Array ();

        for (lightWeight=weight-1;lightWeight>-1;lightWeight--)
            {
            digitB=digits[lightWeight];

            if (digitB==digitA) continue;
            valueDifference=(digitA-digitB)*(-Math.pow(10,weight)+Math.pow (10,lightWeight));
            if (valueDifference>0) biggerValue.push(valueDifference);
            }

        if (biggerValue.length>0)
            {
            biggerValue.sort();
            return (biggerValue[0]+num);
            }
        }
    }
网友答案:

this is the solution I figured out for the problem without using a recursive function. It's passed all the tests on coderbyte. I am still new to this so using recursion is not the first thing I look for. hope this can help anyone else looking for a solution.

function PermutationStep(num) {
  var numArr = (num + '').split('').sort().reverse();
  var numJoin = numArr.join('');
  for (var i = (num + 1); i <= parseInt(numJoin); i++){
    var aaa = (i + '').split('').sort().reverse();
    if (aaa.join('') == numJoin){
    return i;
    }
  }
  return -1;
}
相关阅读:
Top