"""
Сложность: O(n!) (основанием здесь можно пренебречь)
Название: факториальное время

Яркий пример: Задача коммивояжера

Это факториальная временная сложность.
Каждое действие требует вычисления всех перестановок в коллекции
и итоговое время выполнения действия вычисляется как факториал исходной коллекции
Это очень большое расчетное время и неоптимальный алгоритм

Рассмотрим пример, в котором выводятся все возможные комбинации элементов списка
В основе алгоритма выбор на каждом этапе пары элементов,
 чтобы выполнить каждую замену этих элементов только один раз

Итоговое время будет расти факториальным образом,
в зависимости от размера входных данных, поэтому мы можем сказать,
что алгоритм имеет факторную сложность времени O(n!).
"""


def func_calc(lst, n):
    if n == 1:
        print(lst)
        return

    for i in range(n):
        func_calc(lst, n - 1)
        if n % 2 == 0:
            lst[i], lst[n - 1] = lst[n - 1], lst[i]
        else:
            lst[0], lst[n - 1] = lst[n - 1], lst[0]


lst = [1, 2, 3]
func_calc(lst, len(lst))

3155c3e480dc7e808f6ba2f994ff804c973a22fb
<mask token>

<mask token>


def func_calc(lst, n):
    if n == 1:
        print(lst)
        return
    for i in range(n):
        func_calc(lst, n - 1)
        if n % 2 == 0:
            lst[i], lst[n - 1] = lst[n - 1], lst[i]
        else:
            lst[0], lst[n - 1] = lst[n - 1], lst[0]


<mask token>

<mask token>


def func_calc(lst, n):
    if n == 1:
        print(lst)
        return
    for i in range(n):
        func_calc(lst, n - 1)
        if n % 2 == 0:
            lst[i], lst[n - 1] = lst[n - 1], lst[i]
        else:
            lst[0], lst[n - 1] = lst[n - 1], lst[0]


<mask token>
func_calc(lst, len(lst))

<mask token>


def func_calc(lst, n):
    if n == 1:
        print(lst)
        return
    for i in range(n):
        func_calc(lst, n - 1)
        if n % 2 == 0:
            lst[i], lst[n - 1] = lst[n - 1], lst[i]
        else:
            lst[0], lst[n - 1] = lst[n - 1], lst[0]


lst = [1, 2, 3]
func_calc(lst, len(lst))

"""
Сложность: O(n!) (основанием здесь можно пренебречь)
Название: факториальное время

Яркий пример: Задача коммивояжера

Это факториальная временная сложность.
Каждое действие требует вычисления всех перестановок в коллекции
и итоговое время выполнения действия вычисляется как факториал исходной коллекции
Это очень большое расчетное время и неоптимальный алгоритм

Рассмотрим пример, в котором выводятся все возможные комбинации элементов списка
В основе алгоритма выбор на каждом этапе пары элементов,
 чтобы выполнить каждую замену этих элементов только один раз

Итоговое время будет расти факториальным образом,
в зависимости от размера входных данных, поэтому мы можем сказать,
что алгоритм имеет факторную сложность времени O(n!).
"""


def func_calc(lst, n):
    if n == 1:
        print(lst)
        return

    for i in range(n):
        func_calc(lst, n - 1)
        if n % 2 == 0:
            lst[i], lst[n - 1] = lst[n - 1], lst[i]
        else:
            lst[0], lst[n - 1] = lst[n - 1], lst[0]


lst = [1, 2, 3]
func_calc(lst, len(lst))
