Перестановки в Python с фиксированными позициями: itertools и примеры

Руководство по перестановкам в Python с фиксированными позициями: примеры с itertools.permutations, функция для нескольких индексов и советы по оптимизации.

Генерировать перестановки в Python довольно просто, но в реальных задачах часто есть ограничения: какие‑то позиции должны оставаться фиксированными, а остальные можно переставлять. В этом руководстве показано, как обработать один фиксированный индекс, а затем обобщить подход на несколько фиксированных индексов с помощью itertools.permutations.

Постановка задачи: перестановка с фиксированным индексом

Предположим, у вас есть последовательность, и вы хотите переставлять только подвижные элементы, оставляя конкретный индекс неизменным. Ниже — минимальный пример, в котором третий элемент остаётся на месте, а остальные переставляются.

from itertools import permutations
nums = [5, 6, 7, 9]
pin_idx = 2  # оставить 7 на индексе 2 и переставлять [5, 6, 9]
free_slice = nums[:pin_idx] + nums[pin_idx + 1:]
perm_iter = permutations(free_slice)
accum = []
for tup in perm_iter:
    accum.append(list(tup))
for candidate in accum:
    candidate.insert(pin_idx, nums[pin_idx])
print(accum)

Этот код создаёт все перестановки подвижных элементов, а затем возвращает фиксированное значение на его исходную позицию. Для одного фиксированного индекса это работает отлично.

Что здесь происходит и почему это работает

Идея проста и надёжна: удаляем значения на фиксированных позициях, генерируем перестановки для всего остального и вставляем фиксированные значения обратно на их исходные индексы. Поскольку permutations затрагивает только сокращённый набор, элементы на закреплённых позициях не двигаются, а все корректные размещения оставшихся значений перебираются.

Когда вы масштабируете это на несколько фиксированных индексов, логика та же: изолируйте все индексы, которые нельзя трогать, переставляйте только остальные значения и возвращайте фиксированные на свои места в каждой сгенерированной перестановке.

Обобщённое решение для нескольких фиксированных индексов

Следующая функция инкапсулирует этот шаблон для любого набора фиксированных индексов. Она использует itertools.permutations для перестановок неприкреплённой части и затем вставляет закреплённые значения обратно.

from itertools import permutations
def lock_positions_perms(items: list, pinned_pos: list[int] | None = None) -> list[list]:
    """
    Построить все перестановки входной последовательности, сохраняя элементы
    на указанных позициях неизменными.
    :param items: последовательность для перестановки
    :param pinned_pos: индексы, которые должны оставаться на исходных позициях
    :return: список перестановок с сохранением фиксированных позиций
    """
    pinned_pos = [] if pinned_pos is None else pinned_pos
    movable_vals = [val for idx, val in enumerate(items) if idx not in pinned_pos]
    all_arrangements = [list(t) for t in permutations(movable_vals)]
    for arrangement in all_arrangements:
        for pos in pinned_pos:
            arrangement.insert(pos, items[pos])
    return all_arrangements
print(lock_positions_perms(["a", "b", "c", "d", "e"], pinned_pos=[1, 3]))
# [['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'e', 'd', 'c'], ['c', 'b', 'a', 'd', 'e'],
#  ['c', 'b', 'e', 'd', 'a'], ['e', 'b', 'a', 'd', 'c'], ['e', 'b', 'c', 'd', 'a']]

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

Примечания к поведению и компромиссам

В текущем виде функция материализует весь набор результатов, заранее полностью потребляя itertools.permutations. Её можно адаптировать для поэлементной выдачи: вставлять закреплённые значения на лету и использовать yield вместо возврата полного списка. Также, поскольку обратная вставка выполняется для каждой полученной перестановки, такой подход может быть не самым эффективным. Более быстрая альтернатива неочевидна без реализации собственной процедуры перестановок.

Зачем это нужно

Перестановки с ограничениями полезны, когда в структуре данных есть «якоря», которые нельзя смещать, а остальные элементы можно исследовать исчерпывающе. Этот приём сохраняет код ясным, позволяет выражать ограничения через индексы и опирается на хорошо проверенный инструмент стандартной библиотеки — itertools.permutations.

Выводы

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