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

Reescreva o algoritmo L tal que produza todas as permutações de a1... an em "reverse colex order", isto é, encontrar a ordem lexicográfica decrescente da sequência an ... a1.

0 votos
41 visitas
perguntada Jun 30 em Ciência da Computação por claudiaeirado (46 pontos)  
editado Jun 30 por claudiaeirado

O Exercício 2 está descrito na página 344 do livro The Art of Computer Programming, Volume 4A: Combinatorial Algorithms – Donald E. Knuth.

Compartilhe

1 Resposta

+1 voto
respondida Jun 30 por claudiaeirado (46 pontos)  
editado Jul 3 por claudiaeirado

O Algoritmo L está descrito na página 319 do livro The Art of Computer Programming, Volume 4A: Combinatorial Algorithms – Donald E. Knuth.

Segundo Donald Knuth, o algoritmo remete a Narayana Pandita, criado no século XIV na Índia. Em matemática, uma ordem lexicográfica, (também conhecida como ordem do dicionário, ordem alfabética ), é uma estrutura de ordem natural do produto cartesiano de dois conjuntos ordenados.

Algoritmo L (Geração de Permutações Lexicográficas, tradução nossa):

Dada uma sequência de \(n\) elementos \(a_{1}, a_{2}, \ldots , a_{n}\), inicialmente ordenada tal que
\[a_{1} \leq a_{2} \leq \ldots \leq a_{n},\]
este algoritmo gera todas as permutações de \( \{ a_{1}, a_{2}, \ldots , a_{n} \} \), visitando-as em ordem lexicográfica. Por exemplo, as permutações de \( \{1,2,2,3\} \) são
\[ 1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212, 3221,\]
ordenados lexicograficamente. Um elemento auxiliar \( a_{0} \) é assumido para estar presente para conveniência; \( a_{0} \) deve ser estritamente menor que o maior elemento \( a_{n} \).

L1. [Visite.] Visite a permutação \(a_{1} a_{2} ... a_{n}\).
L2. [Ache \(j\).] Faça \( j \leftarrow n-1\). Se \( a_{j} \geq a_{j+1} \), diminua \(j\) por \(1\) repetidamente até que \(a_{j} \lt a_{j+1}\). Termine o algoritmo se \( j=0\).
L3. [Aumente \(a_{j}\).] Faça \( l \leftarrow n \). Se \(a_{j} \geq a_{l}\), diminua \(l\) por \(1\) repetidamente até que \(a_{j} \lt a_{l} \). Então troque \( a_{j} \leftrightarrow a_{l} \).
L4. [Inverta \(a_{j+1}...a_{n}\).] Faça \(k \leftarrow j+1\) e \( l \leftarrow n \). Então, se \( k \lt l\), troque \( a_{k} \leftrightarrow a_{l} \), faça \(k \leftarrow k+1\), \(l \leftarrow l-1\). Retorne para L1. )

Para entender as etapas do algoritmo, seque o link: http://guptamukul.blogspot.com/2009/12/understanding-algorithm-l_05.html

A implementação do Algoritmo L em Python 3.7, segue com uma função que troca os elementos em L3: \( a_{j} \leftrightarrow a_{l} \) e outra função que inverte a sequência em L4 : \( a_{k} \leftrightarrow a_{l} \) e produz \(n-j\) trocas.

print("Algoritmo-L")

Define uma função que faz a troca da posição \( a_{j} \leftrightarrow a_{l} \)

def troca(seq, j, l):
    seq[j], seq[l] = seq[l], seq[j]

Define uma função que inverte a sequencia em L4

def inverte(seq, j, l):
    for i in range((l - j + 1) // 2):
        troca(seq, j + i, l - i)

Define uma função que calcula a próxima permutação

def proxima_permutacao(seq):
    n = len(seq) - 1

#L2: Encontra j tal que seq[j] < seq[j+1]. Finalize se j<0.
    j = n - 1
    while j >= 0 and not seq[j] < seq[j + 1]:
        j -= 1

    if j < 0:
        inverte(seq, 0, n)

#L3:Acha o l tal que seq[j] <= seq[l], então troca os elementos j e l:
    else:
        l = n
        while l > j + 1 and not seq[l] > seq[j]:
            l -= 1
        troca(seq, j, l)

#L4: Inverte os elementos j+1 ... n-1:
        inverte(seq, j + 1, n)
    return seq    

if __name__ == '__main__': 

    import math
#L1: Visite a permutação
    nova=[1, 2, 2, 3]
    tam=len(nova)
    lim=math.factorial(tam)//2
    print(nova)
    if tam>1:
        for offset in range(1,lim): 
                print(proxima_permutacao(nova))

Para a sequência \(\{1,2,2,3\}\), são \( \frac{n!}{(n-2)!} = \frac{4!}{2!} = 12\) permutações, pois há \(2\) repetições na sequência. Caso haja repetições, deve haver uma adaptação para o range. Caso não haja a adaptação, haverá repetição dos valores. O resultado é dado por:
Eis o resultado para a sequência \( \{1,2,2,3\} \):

Algoritmo-L
[1, 2, 2, 3]
[1, 2, 3, 2]
[1, 3, 2, 2]
[2, 1, 2, 3]
[2, 1, 3, 2]
[2, 2, 1, 3]
[2, 2, 3, 1]
[2, 3, 1, 2]
[2, 3, 2, 1]
[3, 1, 2, 2]
[3, 2, 1, 2]
[3, 2, 2, 1]

A solução para o problema 2 da página 344 , de adaptar o algoritmo L para calcular a "reverse colex order" está descrita na página 703 do referido livro, traduzida e implementada no Python.

Considere que \[a_{1} \leq a_{2} \leq \ldots \leq a_{n},\] inicialmente e todas as permutações geradas serão, contudo, em ordem lexicográfica decrescente ou reverse colex order: \[ 1 2 2 3, 2 1 2 3, 2 2 1 3, 1 2 3 2, 2 1 3 2, 1 3 2 2, 3 1 2 2, 2 3 1 2, 3 2 1 2, 2 2 3 1, 2 3 2 1, 3 2 2 1. \] Seja \(a_{n+1}\) um elemento auxiliar maior que \(a_{n}\).

Então segue o algoritmo adaptado:

M1. [Visite.] Visite a permutação \(a_{1} a_{2} ... a_{n}\).
M2. [Ache \(j\).] Faça \( j \leftarrow 2\). Se \( a_{j-1} \geq a_{j} \), aumente \(j\) por \(1\) até que \(a_{j-1} \lt a_{j}\). Termine o algoritmo se \(j \gt n\).
M3. [Diminua \(a_{j}\).] Faça \( l \leftarrow 1\). Se \(a_{l} \geq a_{j}\), aumente \(l\) até que \(a_{l} \lt a_{j}\).Então troque \( a_{l} \leftrightarrow a_{j} \).
M4. [Inverta \(a_{1} \ldots a_{j-1}\).] Faça \(k \leftarrow 1\) e \( l \leftarrow j-1\). Então, se \(k \lt l\), troque \( a_{k} \leftrightarrow a_{l} \), faça\( k \leftarrow k+1\), \(l \leftarrow l-1\), e repita até que \(k \geq l\). Retorne para M1.

Eis a solução em Python 3.7:

print("Permutações Lexicográficas Decrescentes - Exercício 2")
def troca(seq, j, l):
    seq[j], seq[l] = seq[l], seq[j]


def inverte(seq, j, l):
    for offset in range((l - j +1) // 2):
        troca(seq, j + offset, l - offset)


def proxima_perm(seq):
    n = len(seq) - 1
    j = 1
    while not j > n  and not seq[j - 1] < seq[j]:
        j += 1
    if j > n:
       troca(seq,n,1)
    else:
        l=0
        while  not seq[l] < seq[j]:
            l+= 1
        troca(seq, l, j)
        k=0
        l=j-1
        while k < l:
            k += 1
            l -= 1
        inverte(seq,0,j-1)
    return seq
if __name__ == '__main__': 

    import math
    nova2=[1, 2, 2, 3]
    tam=len(nova2)
    lim=math.factorial(tam)//2
    print(nova2)
    if tam>1:
        for offset in range(1,lim): 
                print(proxima_perm(nova2))

Eis os resultados gerados pelo algoritmo, conforme esperado:

Permutações Lexicográficas Decrescentes - Exercício 2
[1, 2, 2, 3]
[2, 1, 2, 3]
[2, 2, 1, 3]
[1, 2, 3, 2]
[2, 1, 3, 2]
[1, 3, 2, 2]
[3, 1, 2, 2]
[2, 3, 1, 2]
[3, 2, 1, 2]
[2, 2, 3, 1]
[2, 3, 2, 1]
[3, 2, 2, 1]

...