Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como gerar permutações lexicograficamente?

0 votos
15 visitas
perguntada Jul 6 em Ciência da Computação por Victor Candido (21 pontos)  

Como gerar permutação lexicograficamente? Discute cuidadosamente a ideia e implemente o algoritimo para realizar essa tarefa na linguagem de sua preferência, explicitando todos os detalhes da implementação.

Compartilhe

1 Resposta

0 votos
respondida Jul 6 por Victor Candido (21 pontos)  

A ordem lexicográfica é a generalização do modo como a ordem das palavras se baseia na ordem alfabética dos seus componentes verbais. Essa generalização consiste em um total de ordem em toda a ordem de seqüências de elementos do conjunto finito de conjunto. Você pode entender que essa é uma maneira de estabelecer a ordem entre sequências com base em como seus componentes se comparam.

Algorítimo que vamos usar:

Existem várias maneiras de gerar todas as permutações de uma determinada sequência. O algoritmo simples que discutirei aqui é baseado em encontrar a próxima permutação em ordenação lexicográfica, se existir, ou reverter a última permutação para retornar à permutação mínima. Este método remonta a Narayana Pandita na Índia do século XIV.

O Algorítimo é bastante simples e fácil de ser memorizado:

Achar o maior i tal que a[i] < a[i + 1];
Find the biggest j greater than i such that a[j] > a[i]; Swap a[i] and a[j]; Reverse the
elements from a[i + 1] to the last element.

Se a primeira etapa falhar (porque esse índice não existe), a permutação atual é a última.

Dada qualquer permutação de uma lista, isso gera o próximo. Deve-se notar, entretanto, que quando dada a maior permutação lexicográfica, este algoritmo retorna esta mesma permutação, então deve ser verificado para assegurar que se a permutação em questão for a última, nós invertemos a sequência para retornar ao primeiro. permutação.

Este algoritmo é simples de implementar corretamente, computacionalmente eficiente, e gera apenas uma permutação distinta uma vez, o que é conveniente quando existem muitos elementos repetidos.

Agora vamos implementar no python um algorítimo para fazer várias permutações:

def swap(elements, i, j):
elements[i], elements[j] = elements[j], elements[i]


def reverse(elements, i, j):
for offset in range((j - i + 1) // 2):
    swap(elements, i + offset, j - offset)


   def next_permutation(elements):
last_index = len(elements) - 1
if last_index < 1:
    return

i = last_index - 1
while i >= 0 and not elements[i] < elements[i + 1]:
    i -= 1

# If there is no greater permutation, return to the first one.
if i < 0:
    reverse(elements, 0, last_index)
else:
    j = last_index
    while j > i + 1 and not elements[j] > elements[i]:
        j -= 1

    swap(elements, i, j)
    reverse(elements, i + 1, last_index)

E o resultado do nosso algorítimo, após gerar 8 permutações é:

abc, acb, bac, bca, cab, cba, abc, acb, ...

Note que após a sexta permutação, voltamos ao primeiro, pois há apenas seis permutações distintas da string "abc".

Sobre a complexidade do algorítimo:

Este algoritmo usa espaço adicional constante (como é no local) e tem complexidade de tempo linear no pior dos casos, mas é amortizado para tempo constante.

...