Нерекурсивная Наиболее эффективная перестановка Big-O Alghoritm Python3 (не встроенная)

Question

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

Я нашел рекурсивные примеры в Интернете, но это не самый эффективный способ; Я попробовал свой собственный код, но потом понял, что когда я подсчитываю количество возможных перестановок, я фактически делаю свой алгоритм O (! N). Какие-либо предложения? .-.

from random import sample
import time
start = time.time()

testList = list(x for x in range(7))
print('list lenght: %i objects' % len(testList))

nOfPerms = 1
for i in range(1,len(testList)+1):
    nOfPerms *= i
print('number of permutations:', nOfPerms)

listOfPerms = []
n = 1
while n <= nOfPerms:
    perm = tuple(sample(testList, len(testList)))

    listOfPerms.append(perm)
    permutations = set(listOfPerms)

    if len(permutations) == len(listOfPerms):
        n += 1
    else:
        del(listOfPerms[-1])

end = time.time() - start
print('time elapsed:', end)

ВЫВОД:

list lenght: 7 objects
number of permutations: 5040
time elapsed: 13.142292976379395

Если вместо 7 я поставлю 8, 9 или 10, это число перестановок (я не буду показывать время, потому что это занимает слишком много времени):

list lenght: 8 objects
number of permutations: 40320

list lenght: 9 objects
number of permutations: 362880

list lenght: 10 objects
number of permutations: 3628800

Answer 1

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

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

Edit:

Это реализация Python алгоритма Heap, который я обещал (https://en.wikipedia.org/wiki/Heap%27s_algorithm) генерирует N! Перестановок, где генерация каждой перестановки занимает амортизированное O (1) время и использует O (n) пространственную сложность (по альтернативам

def permute(lst, k=None):
    if k == None:

        k = len(lst)

    if k == 1:
        yield lst
    else:
        yield from permute(lst, k-1)

        for i in range(k-1):

            if i % 2 == 0:
                #even
                lst[i], lst[k-1] = lst[k-1], lst[i]
            else:
                #odd
                lst[0], lst[k-1] = lst[k-1], lst[0]
            yield from permute(lst, k-1)


for i in permute([1, 2, 3, 4]):
    print(i)