Какова средняя производительность случая этого алгоритма генерации перестановок?

Question

Я пытаюсь определить среднюю производительность случая этого алгоритма генерации перестановок. Он использует рекурсивный подход, в котором первый элемент заменяется друг на друга, создавая новый набор перестановок - эти наборы затем проходят ту же процедуру, но с фиксированным первым элементом.

Вот код на Python:

# Returns a list of all permutations of the given list.
def permutate(set):
    # A list of all found permutations, to be returned
    permutations = []

    # Takes a set which has all elements below index i fixed and finds all permutations
    def recurse(set, i):
        # If all elements are fixed, store the current permutation
        if i + 1 == len(set):
            permutations.append(set)
        else:
            # Swap the "first" element with each other element to generate new permutations
            for element in xrange(i, len(set)):
                set[element], set[i] = set[i], set[element]
                recurse(set, i + 1)
                set[element], set[i] = set[i], set[element]

    # Use the recursive algorithm to find all permutations, starting with no fixed elements
    recurse(set, 0)
    return permutations

print permutate([1, 2, 3])

У меня нет большого опыта работы с анализируемыми рекурсивными функциями, поэтому я не знаю, как это решить. Если бы мне пришлось сделать предположение, я бы сказал, что время выполнения равно Θ (n!), Потому что множество с n элементами имеет n! перестановки (так что алгоритм должен приложить столько усилий, верно?)

Любая помощь будет оценена.

Answer 1

Прежде всего, сложность O(n!) по причине, указанной в комментарии к вопросу.

Но есть две другие вещи.

1. Не использовать set как имя переменной, потому что вы скрываете встроенный тип данных

2. Ваш алгоритм неверен из-за деталей реализации Python

в нижней части рекурсии вы добавляете результирующую перестановку к permutations переменная. Но список в Python не передается по значению, поэтому вы фактически добавляете ссылку на список ввода. Потому что после recurse завершает свою работу, входной набор находится в том же порядке, в котором он был в начале, поэтому permutation переменная будет хранить n! references в тот же список. Чтобы это исправить, вы можете использовать метод глубокой копии модуля копирования, получившийся код (обратите внимание, что вы можете остановить восстановление, когда i == len(s)):

import copy

# Returns a list of all permutations of the given list.
def permutate(s):
    # A list of all found permutations, to be returned
    permutations = []

    # Takes a set which has all elements below index i fixed and finds all permutations
    def recurse(s, i):
        # If all elements are fixed, store the current permutation
        if i == len(s):
            # append a deepcopy of s
            permutations.append(copy.deepcopy(s))
        else:
            # Swap the "first" element with each other element to generate new permutations
            for element in xrange(i, len(s)):
                s[element], s[i] = s[i], s[element]
                recurse(s, i + 1)
                s[element], s[i] = s[i], s[element]

    # Use the recursive algorithm to find all permutations, starting with no fixed elements
    recurse(s, 0)
    return permutations

print permutate([1, 2, 3])