Блог

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

Я нашел рекурсивные примеры в Интернете, но это, похоже, не самый эффективный способ; Я попробовал свой собственный код, но потом понял, что когда я подсчитываю количество возможных перестановок, я фактически делаю свой алгоритм 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
  

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

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

Редактировать:

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

 
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)