Задание № 26 · ЕГЭ

Построение перестановок перебором

Перебор всех вариантов с выбором элемента и возвратом

2 мин чтенияСложность: Обновлено 29 сентября 2026

Построение перестановок перебором — это способ получить все возможные порядки элементов: на каждом шаге выбирают ещё не использованный элемент, а после завершения ветви возвращаются назад и пробуют следующий вариант. Такой перебор является применением бэктрекинга.

Построение перестановок переборомПерестановка — один из возможных порядков элементов; перебор означает последовательную проверку всех вариантов.

Алгоритм получения всех перестановок множества из \(n\) различных элементов путём последовательного выбора неиспользованного элемента, рекурсивного продолжения выбора и возврата к предыдущему состоянию после завершения ветви.

Как работает алгоритм

Частично построенная последовательность хранится в текущем состоянии. Если её длина равна \(n\), получена готовая перестановка, и её выводят. Иначе перебирают все элементы, которые ещё не были выбраны: добавляют один из них, отмечают использованным, углубляются в рекурсию, а затем отменяют выбор. Возврат нужен, чтобы тот же элемент можно было использовать в другой ветви.

\[P(n)=n\cdot(n-1)\cdot\ldots\cdot 2\cdot 1=n!\]

Число получаемых перестановок \(n!\). На первом шаге возможны \(n\) выбора, на втором — \(n-1\), затем \(n-2\) и так далее. Порядок, в котором рассматриваются кандидаты, задаёт порядок перебора вариантов, но не меняет количество результатов.

№

Пример для элементов A, B, C

Сначала выбираем A. Затем возможны B и C: получаются ветви ABC и ACB. После возврата к первому шагу выбираем B и получаем BAC и BCA, затем C — CAB и CBA. Итого \(3!=6\) перестановок.

Псевдокод

generate(prefix, used):
    if length(prefix) == n:
        print(prefix)
        return
    for each element x:
        if x is not used:
            mark x as used
            generate(prefix + x, used)
            unmark x

Не путайте с сочетаниями

В перестановках важен порядок: ABC и BAC — разные результаты. В сочетаниях порядок выбранных элементов не учитывается. Также возврат не означает удаление уже выведенного результата: отменяется только текущий выбор перед переходом к соседней ветви.

Проверка

Сколько перестановок получится для четырёх различных элементов?

Главное за минуту

Главное

Алгоритм строит последовательность слева направо, выбирая неиспользованный элемент.
После завершения ветви выбор отменяется, и перебор продолжается с другим вариантом.
Для \(n\) различных элементов число перестановок равно \(n!\); тема является частным случаем построения перестановок.