Как сгенерировать размещение по его номеру в лексикографическом порядке?

Question

[tumur4]

Имеем: n = колво эл-ов в перестановке, К = колво эл-ов в размещении, и m = номер размещения. m номер размещения из N по M

Answer 1

[hint000]

1. Организуем список из N элементов по возрастанию;
2. Генерировать будем рекурсивно (это для простоты объяснения, после усвоения идеи можно обойтись циклом);
2.1. Если M==0, то выход из рекурсии;
2.2. Первый элемент размещения - это элемент, находящийся на L-ом месте в списке, где L=((N*m-1)\A(N,M))+1 (нумерация с единицы только для ясности); A(N,M)=число размещений из N по M; удаляем из списка выбранный элемент;
2.3. Для следующего шага рекурсии берём m=m-(L-1)*A(N,M)/N; N=N-1; M=M-1;

Comments

[tumur4]

Не очень понял ход решения, если есть возможность, можете привести решения для данных: N = 9, K = 2, M = 20(номер размещения в лексикографическом порядке).

[hint000]

Тут у вас в вопросе вышла путаница с буквами:

m номер размещения из N по M

Так что я запишу теми буквами, что были раньше:
N=9, M=2, m=20.

Список оставшихся элементов: (1,2,3,4,5,6,7,8,9), ищем размещение: (x1,x2).
A(9,2)=(9!)/(9-2)!=72
L=(9*20\72)+1=3
x1 = (третий элемент в списке) = 3
Список оставшихся элементов: (1,2,4,5,6,7,8,9)
m=9*20%72=36
~~~~~~~~~~~~~ да, тут у меня ошибка...
должно быть m=m-(L-1)*A(N,M)/N=
m=20-2*72/9=20-16=4
N=9-1=8
M=2-1=1
A(8,1)=(8!)/(8-1)!=8
L=(8*4\8)+1
~~~~~~~~ и-и-и тут обнаруживаем ещё одну ошибку
правильно будет вычесть единичку перед целочисленным делением:
L=((N*m-1)\A(N,M))+1
здесь бы вернуться к первому шагу и пересчитать, но там значение L не изменится.
L=31\8+1=4
Напомню, что список у нас: (1,2,4,5,6,7,8,9)
x1 = (четвёртый элемент в списке) = 5
Удаляем этот элемент из списка, хотя это был последний шаг и это уже ни на что не повлияет.
Список оставшихся элементов: (1,2,4,6,7,8,9)
Ответ: (3,5)

P.S. исправляю формулы в ответе.

[tumur4]

Спасибо.

import math
n = int(input()) #число элементов в списке [1, 2, 3 ... n]
k = int(input()) #число элементов в размещении
m = int(input()) #номер размещения
permutation = list(range(1, n + 1))
result = []
while k != 0:
    a = math.factorial(n)/math.factorial(n-k) #количество размещений из n по m
    l = int(((n*m-1)//a) + 1)
    result.append(permutation.pop(l-1))
    m = m - (l-1)*a/n
    n = n - 1
    k = k - 1
print(' '.join(map(str, result)))