Как выбрать все перестановки

Question

Я хочу получить список всех перестановок или рангов перестановок, где элемент ith равен k, а длина больше k и помечена n. Список целых чисел из 1..n должен быть переставлен. Как это можно сделать?

Для первого элемента перестановки это тривиально. Но как это работает для ith Элемента? Итерация по n! перестановкам невозможна.

Answer 1

Прежде всего, обратите внимание, что эта проблема легко может быть преобразована в просто перестановки ранжирования / листинга. Все, что вам нужно сделать, это написать функцию, которая принимает перестановку 1..(n-1) и преобразует ее в перестановку, соответствующую вашим условиям, и наоборот. (Идя в одну сторону, просто увеличьте каждое число в перестановке, которое больше k, и вставьте k в i-ю позицию. Переходя в другое, удалите k и уменьшите все, что больше k.)

Но рейтинг / листинг - это хорошо понятная проблема. См. https://rosettacode.org/wiki/Permutations/Rank_of_a_permutation для решений на нескольких языках, включая три в Python.

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

Answer 2

Предупреждение: длина permutations равна (n-1)!, а общий размер permutations равен O (n*(n-1)!).

import itertools
i,k,n = 1,5,10 #pick these
permutations = [p for p in itertools.permutations(list(range(1,n+1,1))) if p[i]==k]