Перестановки списка в Python без смещения

Question

Итак, допустим, у меня был список: [1, 2, 3]

Перестановки такого списка были бы [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] и [3, 2, 1]

(группа 1) Однако, скажем, мы смотрим на расположение[1, 2, 3].Если мы сдвинем его на единицу, мы получим [3, 1, 2].Сделайте это снова, и мы получим [2, 3, 1].

(Группа 2) Если мы посмотрим на расположение [1, 3, 2] и сместим его на единицу, мы получим [2,1, 3].Еще один, и мы получаем [3, 2, 1].

Обе эти группы аранжировок составляют перестановки списка.

Мои вопросы, если это можно использовать для ускорениягенератор перестановок, чем перестановки из itertools.

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

(Примечание: я понимаю, чтобыло бы бесполезно, если бы в списке было только три элемента, но список мог бы иметь различное количество размеров, например 25 или 100).

Answer 1

Я не знаю, есть ли у вас опыт работы в области компьютерных наук, но то, что вы описываете, известно как Проблема коммивояжера .

Предлагаемое вами решение является алгоритмом "грубой силы" и не масштабируется более чем на пару пунктов.Есть альтернативные алгоритмы, которые являются более эффективными.Если вам необходимо рассчитать точный оптимум, взгляните на раздел Exact Algorithms в связанной статье.Если хорошее решение «достаточно хорошее», вы также можете использовать эвристику, чтобы сократить время выполнения.