Next Bigger Number

while

const {log} = console;

/*
    n(abcde): 
      代表下一個比 abcde 大的數字 (但還是只能用 abcde 這幾個數字)。
      
    f(abcde): 
      1. 代表在 bcde 內找出「比 a 大的數字最小者」，然後跟 a 對調，
         如果找不到，就回傳 undefined。
      2. 對調後，後面的數字「從小排到大」，跟第一個數字接起來，然後回傳。
      
    n(abcde) = abc+f(de) || ab+f(cde) || a+f(bcde) || f(abcde)
*/

// assume: `k` -> string of digits.
// suppose k = abcd, b = next bigger digit than `a`, then:
// f(abcd) = b + smallest(acd)
function f(k) {
    
    // 1. find next bigger digit than leading digit
    let arr = k.substring(1).split('').sort();  // sort is key
    let i = arr.findIndex(c => +c > +k[0]);
    
    // 2. if not found, return undefined.
    if (i === -1) return undefined;
    
    //    if found, interchange them.
    let b = arr[i]; arr[i] = k[0];
    return b + arr.sort().join('');             // remember to sort again
}

// assume: `k` -> string of digits.
// next bigger number
function n(k) {
    
    let next;
    let left = k.length - 2;
    
    while (!next && left >= 0) {
        let found = f(k.substring(left));
        if (found) next = k.substring(0, left) + found;
        left -= 1;
    }
    
    return next;
}

// -------- log --------

// f(k)
[
    3412,           // 4123
    4312,           // undefined
]
    .map(n => f(String(n)))
    .forEach(x => log(x));

// n(k)
[
    3412,           // 3421
    4312,           // 4321
    59884848459853, // 59884848483559
]
    .map(k => n(String(k)))
    .forEach(x => log(x));

recursive

const {log} = console;

/*
  Next bigger number with the same digits
  https://www.codewars.com/kata/55983863da40caa2c900004e
  
  下一個數字：
      next(abcd)
      
  不是：「a 不用動，然後在 bcd 內找下一個數字」
      a + next(bcd)
      
  不然就是：「從 bcd 調一個剛好比 a 大的數字上來，然後剩下數字由小到大排」
      b + first(acd) = f(abcd)
      
  也就是：(n 代表 next)
      n(a)  = undefined (x)
      
      n(ab) = a+n(b) || f(ab)
            =    x   || f(ab) 
            =           f(ab)
      ⭐️ 從此例知道：我們只要定義 n(a) = undefined，其他狀況都會自動推演。
      
      n(abcd) 
      = a+n(bcd) || f(abcd)
      = a+(b+n(cd) || f(bcd)) || f(abcd)
*/

// f(abcd) = b + first(acd)
// where:
//     b = next bigger digit than `a`
//
// assume: `k` -> string of digits.
function f(k) {
    
    // 1. find next bigger digit than leading digit
    let arr = k.substring(1).split('').sort();          // sort is key
    let i = arr.findIndex(c => +c > +k[0]);
    
    // 2. if not found, return undefined.
    if (i === -1) return undefined;
    
    //    if found, interchange them.
    let b = arr[i]; arr[i] = k[0];
    return b + arr.sort().join('');                     // remember to sort again
}

// assume s is a "String" of digits
// n(abcd) = a + n(bcd) || f(abcd)
function next(s){
  
  // ⭐️ base cases:
  if (s.length <= 1) return undefined;
  
  // ⭐️ recursive case:
  let found = next(s.substring(1));
  return (found) ? s[0] + found : f(s);
}

// main
function nextBigger(n){ 
  let s = next(String(n))
  return s ? +s : -1; 
}

// -------- log --------

[
  (2017),             // 2071
  (715801),           // 715810
  (9999999999),       // -1
  (70168141041296),   // 70168141041629
  
]
  .map(n => nextBigger(n))
  .forEach(x => log(x));

📗 參考

• codewars ⟩ Next Bigger Number

💾 程式

• codepen ⟩

  • next bigger? - 用「由內而外」的演算法。(while)

  • next bigger number? - 用「由外而內」的演算法。(recursive)