Trabalhando com permutações em ordem lexicográfica crescente

Digamos que com os inteiros de 1 a N escrevemos todas as possíveis permutações em ordem crescente. Aprenda a calcular a posição de uma dada permutação e a permutação de uma dada posição! Ideias importantes em problemas de matemática e computação

[ Hits: 1.656 ]

Por: Vitor Marques Rodrigues em 24/11/2020


Qual a permutação de uma dada posição?



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.

Página anterior    

Páginas do artigo
   1. Introdução
   2. Básico de Análise Combinatória
   3. Qual a posição de uma dada permutação?
   4. Qual a permutação de uma dada posição?
Outros artigos deste autor
Nenhum artigo encontrado.
Leitura recomendada

Gerar senhas seguras com Python

Python + ADB

Clicador automático de Tinder com Python

Como criar um bot para curtir e comentar perfis do Instagram

paramiko - Python + SSH

  
Comentários
[1] Comentário enviado por mauricio123 em 25/11/2020 - 13:03h


Ficou top.

___________________________________________________________
[code]Conhecimento não se Leva para o Túmulo.
https://github.com/MauricioFerrari-NovaTrento [/code]


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts