Как, имея число, получить близжайшее большее число, состоящее из тех же цифр?

Question

[dmitriyivvvv]

Имеется ли алгоритм нахождения ближайшего большего числа из цифр исходного числа? Например, дано исходное число 7809, его ближайшее большее будет 7890. Так вот, существует ли такой алгоритм или придется выполнять все возможные перестановки цифр в этом числе и сохранять те которые больше исходного, чтобы затем отсортировать и вывести наименьшее?
Например, число 47651270590822 следующее большее из цифр исходного числа 47651270592028.

Answer 1

[dmitriyivvvv]

Ответ найден если кому то интересно, то вот он:
двигаемся справа налево в поисках цифры которая будет меньше предыдущей. Например для 534976 это будет 4. Затем справа от этой цифры ищем наименьшее число которое будет больше этой цифры (> 4) в данном случае это 6>4.Поменяйте их местами. Получим 536974, затем отсортируйте по возрастанию числа после 6 (в данном случае 974 => 479) получим искомое число 536479

Answer 2

[Lander]

Логически рассуждайте.
Ближайшее большее может отличаться в младших разрядах. Поэтому алгоритм следующий:
1. n = 2
2. Берёте n младших разрядов и переставляете их местами.
3. Сравниваете с начальным, если результат не достигнут, то n++ и п.2.
4. Число найдено.

Comments

[dmitriyivvvv]

Например число 47651270590822 следующее большее из цифр исходного числа 47651270592028
можете описать по шагам?

[Lander]

dmitriyivvvv,

переставляете их местами.

Замените у себя в голове на "сортируете в порядке убывания", а всё остальное то же самое.

[dmitriyivvvv]

не работает ваш алгоритм верхнее число тому пример@usdglander,

[Lander]

dmitriyivvvv, А, да, вы правы. Простой сортировкой хвоста тут не обойтись... Щас докрутим. :)

Answer 3

[Сергей Соколов]

Upd. Алгоритм ниже неверный, т.к. не работает в случае, когда необходимо переставить сразу несколько цифр.

Рассматриваем пары неодинаковых цифр в числе.
Взаимной их перестановкой можно увеличить число только когда левая цифра меньше правой. 23 -> 32
Размер увеличения тем меньше, чем правее обе цифры. Они могут идти и не подряд, а, скажем, через одну.

Коэффициент, который требуется минимизировать – это десятичное число из нулей с единицами в этих позициях. Скажем, лучше поменять позиции 2 и 3, чем 4 и 1, т.к. 110 < 1001 Т.е. при переборе позиций меньше всего хотим двигать левую позицию, пока не переберем все варианты правой:

Варианты для 4

0011
0101
0110
1001
1010
1100

Отсюда алгоритм.

1. справа налево перебираем пары цифр пока не найдётся первая пара, где
   левая меньше правой
   
2. меняем их местами.
   

Всё.

Comments

[Сергей Соколов]

алгоритм-то неправильный. Для примера 0822 он даст 2820, когда можно меньше, как вы и написали, 2028 :-(

[dmitriyivvvv]

Сергей Соколов, ага я уже заметил, не все так просто как кажется на первый взгляд

[dmitriyivvvv]

Сергей Соколов,Я нашел алгоритм на одном из англоязычных сайтов, если вам интересно то вот он:
двигаемся справа налево в поисках цифры которая будет меньше предыдущей. Например для 534976 это будет 4. Затем справа от этой цифры ищем наименьшее число которое будет больше этой цифры (> 4) в данном случае это 6>4.Поменяйте их местами. Получим 536974, затем отсортируйте по возрастанию числа после 6 (в данном случае.) получим искомое число 536479

[res2001]

В вашем алгоритме для приведенного примера получается не верный ответ:
47651270590822 => 47651270598022
должно быть: 47651270592028

1.Справа налево ищем цифру меньшую самой правой цифре. (пусть позиция меньшей цифры будет i)
2.меняем их местами (меньшую и самую правую)
3.сортируем в порядке возрастания цифры в позициях от i+1 до конца
4.Если цифры меньше правой нет, то правой цифрой считаем цифру в предпоследней позиции и повторяем п.1-3, при этом сортировать нужно все цифры.
Все!

[dmitriyivvvv]

res2001,
47651270590822
47651270592802
47651270592028

все работает перепроверьте,
если вы это мне конечно написали

[res2001]

Долго писал комментарий :-)
dmitriyivvvv, Не нужно делать второй шаг - просто меняйте с любой предыдущей цифрой (с последней в моем варианте) - все равно потом сортировать.

Еще добавлю:
Если в числе цифры упорядочены по убыванию, то задание не выполнимо - имеем самое большое число из имеющихся цифр. Для выполнения задания нужно добавлять еще один разряд.

[res2001]

dmitriyivvvv, про неработающий алгоритм относилось автору ответа.

[dmitriyivvvv]

res2001, ваш алгоритм дал осечку
52174920893
52174923890
52174923089
а должно быть
52174920938

[res2001]

dmitriyivvvv, Согласен, тогда немного изменим:
1.Справа налево перебираем пары цифр пока не найдётся первая пара, где левая меньше правой
(пусть позиция левой цифры будет i)
2.меняем их местами
3.сортируем в порядке возрастания цифры в позициях от i+1 до конца

PS: Ваш алгоритм и мой - практически одно и то же. Только в вашем, по моему, второй шаг лишний - нет необходимости искать "справа от этой цифры наименьшее число которое будет больше этой цифры" - просто меняем местами пару чисел и сразу сортировка - результат одинаков.

Answer 4

[Сергей]

Сортировка по возрастанию \ убыванию? после чего берутся предыдущее и следующее числа возле Х (7809) и сравниваются.

Answer 5

[uvelichitel]

Рассматривая число как массив цифр
1 Ищем цифру меньшую последней (при сравнениях можно делать перестановки например как в сортировке пузырьком)
2. Переставляем найденную цифру с пузырьком.
3. Сортируем хвост от найденной позиции(например той же сортировкой пузырьком за простоту алгоритма)
1.
903822
903822
903282
902382
За четыре сравнения найден 0
2.
920382
Переставка пузырька с 0
3.
920328
920238
Досортировка