kitscribe
@kitscribe
Хаброжитель

Где ошибка в алгоритме пермутаций?

Нужно написать функцию, которая вернёт ближайшее большее число к числу ей переданному, выполнив пермутации.

Мой код проходит не все тесты. В чём я ошибся с алгоритмом? И как это можно исправить?

Код

def next_bigger(n):
    origin = n
    n = list(str(n))

    for i in range(len(n), 0, -1):
        n2 = n[::]
        n2[i - 2] = n[i - 1]
        n2[i - 1] = n[i - 2]
        
        if int("".join(n2)) > origin:
            return int("".join(n2))
    return -1

if __name__ == "__main__":
    print(next_bigger(12)) #   -> 21
    print(next_bigger(144)) # -> 414
    print(next_bigger(1234567890)) # -> 1234567980! должно быть 1234567908

  • Вопрос задан
  • 130 просмотров
Решения вопроса 2
@o5a
Алгоритм должен быть такой: с конца ищем первый символ, такой, что a[i] < a[i+1], так мы определяем наименьший разряд, который сделает число больше предыдущего. Затем нам нужно минимизировать "хвост", чтобы получилось число, ближайшее к исходному (чем меньше хвост, тем оно ближе к исходному). Для этого мы хвост сортируем по возрастанию и переставляем наше число наименьшего разряда с первым числом из хвоста, большим его.

В примере с 1234567890.

1. Ищем цифру наименьшего разряда, когда a[i] < a[i+1]. Это 8, хвост [9, 0].
2. Сортируем хвост [0, 9] и идем по нему в поисках первой цифры, большей нашей 8. Это 9.
3. Переставляем их и возвращаем результат
1234567809 => 1234567908
Ответ написан
@Andy_U
Количество перестановок множества длиной N равно N! (факториал). У вас цикл длиной N, т.е. вы не все варианты перебираете. Может быть, конечно, что можно перебирать не все варианты, но из последнего примера явно следует, что одиночными попарными рокировками не обойтись.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы