Как вывести следующие большее число образованное теми же цифрами?

Question

Мне нужно написать функцию которая принимает число и возвращает следующее большее число, образованное по тем же цифрам. Например:

23 => 32
624 => 642
2018 => 2081
3022 => 3202

У меня есть только вариант перебрать все возможные комбинации этих четырёх чисел и найти наиболее приближенные к нужному числу, но может есть какое-то другое решениe? Спасибо!

Answer 1

По сути вам нужно отсортировать по убыванию цифры в составе числа. Наибольшее это отсортированное до конца, а все предыдущие перестановки заведомо меньше.

Answer 2

Эта задача эквивалентна нахождению следующей перестановки в лексикографическом порядке. В библиотеках некоторых языков есть средства типа std:: next_permutation в С++.

Хорошее описание алгоритма получения следующей перестановки можно прочитать, например, здесь, суть его:

Найти ближнюю к концу пару соседей, у которых нарушен порядок 
   array[i − 1] < array[i]

Найти самый большой индекс j такой, что j ≥ i  и array[j] > array[i − 1]

Обменять array[j] и array[i − 1]

Перевернуть суффикс массива, начиная с индекса i

Код на JS:

function nextPermutation(array) {
    // Find non-increasing suffix
    var i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i])
        i--;
    if (i <= 0)
        return false;
    
    // Find successor to pivot
    var j = array.length - 1;
    while (array[j] <= array[i - 1])
        j--;
    var temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;
    
    // Reverse suffix
    j = array.length - 1;
    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }
    return true;
}

// Example:
arr = [0, 1, 0];
nextPermutation(arr);  // (returns true)
console.log(arr);

Answer 3

const swap = (arr, ai, bi) => {
  arr[ai] = arr[bi] - arr[ai]
  arr[bi] = arr[bi] - arr[ai]
  arr[ai] = arr[ai] + arr[bi]
}

const arrSortPart = (arr, sortAfterIndex, sortFn) => {
  const sortedArr = arr.slice(sortAfterIndex)
  sortedArr.sort(sortFn)
  sortedArr.forEach((val, i) => {
    arr[sortAfterIndex + i] = val
  })
}

function nextBigger(n) {
  const nums = Array.from(`${n}`).map(i => Number(i))

  let i = nums.length - 1

  while (i >= 0) {
    const li = i - 1
    const left = nums[li]
    const right = nums[i]

    if (left < right) {
      for (let j = nums.length - 1; j >= i; j--) {
        const jnum = nums[j]
        if (left < jnum) {
          swap(nums, li, j)
          arrSortPart(nums, i, (a, b) => a - b)
          return Number(nums.join(''))
        }
      }
    }

    i--
  }

  return -1
}

const test = 4365
// const test = 5346
// const test = 144
const res = nextBigger(test)

console.log('res', test, res)

БЛОГ НА HUSL

Как вывести следующие большее число образованное теми же цифрами?

Ответы (3 шт):