Raciocínio

Qual posição ocupa o número 10? Bom, é óbvio que é a 10a posição, porém há um raciocínio nisso que nos ajudará na nossa pergunta. O número 10 ocupa a 10a posição, pois há 9 números antes dele.

Analogamente a permutação [1,3,2,4] ocupa a 3a posição, pois há duas permutações antes dela ([1,2,4,3] e [1,2,3,4]). Ou seja, para contar qual posição ocupa uma dada permutação vamos contar quantas permutações são menores que ela e depois somar 1.

Vamos entender a lógica matemática do processo e depois escrever o algoritmo.

Qual posição ocupa a permutação [4,2,3,1]? Vamos lá!

Lógica matemática

1) Com começo 423_. Não há nenhuma menor que 4231, pois só é possível formar 4231.

2) Com começo 42__. Precisamos escolher um número para a 3a posição que seja menor que 3 entre os números anteriores, no caso {1}. Podemos escolher o 1 para a 3a posição e depois o 3 para a 4a. Logo 1 permutação menor que 4231 com começo 42.

3) Com começo 4___. Precisamos escolher um número para a 2a posição que seja menor que 2 dentre os anteriores, no caso {1,3}. Há apenas uma opção para a 2a posição, o número 1. Escolhido o 2o algarismo podemos escolher os outros de 2! maneiras (4123 ou 1232), pois os algarismo restantes são {2,3} há 2 opções para o 3o algarismo e 1 opção para a última posição. Logo 1x2! = 2 permutações menores que 4231 com começo 4.

4) Agora sem começo específico____. Precisamos escolher um número menor que 4 dentre {1,2,3}. Os três são menores que 4, logo há 3 opções. Feito a escolha do primeiro algarismo, podemos escolher os restantes de 3! maneiras. Logo há 3x3!=18 permutações sem começo específico menores que 4231.

Somando tudo = 1 + 2 + 18 = 21

Precisamos somar mais um para sabermos a posição final: 21 + 1 = 22

Logo a permutação [4,2,3,1] ocupa a posição 22.

Algoritmo

Agora vamos entender bem o que fizemos. Contamos por partes, primeiro com começo 423, depois 42, depois 4 e depois sem começo específico. Os faltando apenas o último algarismo (Começo 423) nunca terão permutações menores, pois só há uma opção para o último algarismo que forma a permutação dada, logo sempre podemos ignorar. O que fizemos foi basicamente:

-------------------------------------X-------------Y--------------Z
Quantos números
menores que:___________3________2________4

Entre:_______________{1}______{1,3}_____{1,2,3}

		Resposta = X*1! + Y*2! + Z*3! + 1

No caso X = 1, Y = 1, Z = 3.

Basicamente o algoritmo é o seguinte:

• Percorremos o número de trás para frente. Digamos que estamos no algarismo A.
• Adicionamos A a lista de anteriores.
• Checamos o número a frente de A. Digamos B.
• Calculamos a quantidade de números menores que B dentre os anteriores (função count).
• Multiplicamos essa quantidade pelo quantidade de números em anteriores.
• Fazemos isso com todos os algarismos menos o primeiro.
• Somamos esses resultados parciais.
• Somamos 1.

Vamos fazer isso em código agora.

Código em Python

from math import factorial

def count(n, li):
    i = 0
    for k in li:
        if k < n:
            i += 1
    return i

def find_pos(li):
    anteriores = []
    resultado = 0
    for c in range(len(li)-1, 0, -1):
        a.append(li[c])
        B = li[c-1]
        resultado += factorial(len(anteriores))*count(B, anteriores)
    return resultado+1