Какой абстрактный тип данных (ADT) используется для реализации алгоритма steinhaus-johnson-trotter (перестановки) в Python?

Question

Какой абстрактный тип данных (ADT) используется для реализации steinhaus-johnson-trotter algorithm для генерации перестановок объектов в Python?

Я особенно беспокоился о стоимости сложности вставки в любом месте данных:

1 

12 
21 

123 
132 
312 

Вдвойне связанный список из llist модуля является хорошим выбором?

Answer 1

Вам не нужно вставлять новые элементы в последовательность, вам нужно всего лишь менять два элемента каждый раз. Это быстро на массиве. Стандартный список Python реализован как массив, см. https://wiki.python.org/moin/TimeComplexity, поэтому я считаю, что это лучшая структура данных для этой цели.