Raciocínio

Vamos fazer por partes, encontrar o primeiro algarismo, depois o segundo, depois o terceiro e assim por diante.

Qual permutação ocupa a 16a posição?(Estamos considerando permutações de {1,2,3,4} em ordem lexicográfica crescente).

Lógica matemática

Precisamos encontrar a permutação que tem 15 números antes. Vamos descobrir o primeiro algarismo. Para isso vamos testando. Com começo 2 haverá pelo menos 3! = 6 números antes dele, que são os começados por 1. Com começo 3 haverá pelo menos 2x3! = 12 números antes dele, os com começo 1 ou 2. Com começo 4, haverá pelo menos 3x3! = 18 números antes dele, os com começo 1, 2 ou 3. Ou seja:

Começo_________A = Pelo menos quantos números antes
	1________________________0
	2________________________6
	3________________________12
	4________________________18

Como estamos procurando pela 16a posição, concluímos que o começo é com o número 3, pois é o maior começo possível em que A é menor ou igual a 15.

Escolhido o primeiro algarismo, nos resta {1,2,4} e 15 - 12 = 3 posições a serem preenchidas. Com segundo algarismo 2 há pelo menos 2! = 2 números antes (os com segundo algarismo igual 1). Com segundo algarismo igual a 4 há pelo menos 2x2!=4(os com com segundo algarismo igual a 2 ou 1).

Com segundo algarismo________B = Pelo menos quantos números antes

		   1__________________________0
		   2__________________________2
		   4__________________________4

Novamente concluímos que o segundo algarismo deve ser 2, pois é o máximo algarismo em que B é menor ou igual a 3.

Feito isso nos restam {1,4} e 3- 2 = 1, posições a serem preenchidas.

Fazendo o quadro do terceiro algarismo:

Com terceiro algarismo_________C = Pelo menos quantos números antes

		1_____________________________0
		4_____________________________1

Concluímos que o terceiro algarismo é o 4. Nos restando 1-1 = 0 posições e o algarismo 1. Implicando que o último algarismo é o 1.

Formamos nossa permutação [3,2,4,1].

Algoritmo

Vamos definir a função recursivamente

• Ela vai receber três parâmetros:
  n → número da posição (consequentemente n-1 será o número de posições que precisamos preencher)
  li → lista com os números que ainda temos disponíveis.
  a → lista de algarismos definidos nas suas respectivas ordens (começa vazia)

Fazemos o seguinte:

• Organizamos a lista em ordem crescente
• Calculamos x.
  x < n/factorial(len(li)-1). X tem que ser o maior inteiro possível. Ele representa a quantidade de números menores que o escolhido dentre os presentes em "li".
• Adicionamos o escolhido a "a"
• Retiramos o escolhido de "li"
• Retiramos de "n" a quantidade de posições preenchidas
• Retornamos a função com os novos parâmetros
• Quando chegarmos no último algarismo a ser escolhido retornamos a permutação formada no caso "a".

Código

def find_num(n,li,a=[]):
    li.sort()
    y = len(li) - 1
    x = n/factorial(y)
    if int(x) == x:
        x = int(x) - 1
    else:
        x = int(x)
    a.append(li[x])
    li.pop(x)
    if y == 0:
        return a
    n -= x*factorial(y)
    return find_num(n, li, a)

Conclusão

Basicamente é isso. Obrigado por ter lido. Até mais.