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.657 ]

Por: Vitor Marques Rodrigues em 24/11/2020


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



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

Página anterior     Próxima página

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

Breve Estudo Sobre Ransomwares e Análise Estática/Dinâmica do WannaCry

Construindo um portscanner TCP com Python

Python - Threads

Como criar um keylogger em Python

Como baixar vídeos do Facebook via terminal

  
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