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

Explique como fazer o Algoritmo L rodar mais rápido, racionalizando suas operações quando o valor de j está próximo de n.

+2 votos
73 visitas
perguntada Jun 30 em Ciência da Computação por claudiaeirado (51 pontos)  

O Exercício 1 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 (51 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.

Mede o tempo de execução do algoritmo

print("Algoritmo-L")
import time
inicio = time.time()

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 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=[0,1,2,3]
    tam=len(nova)
    lim=math.factorial(tam)
    print(nova)
    if tam>1:
        for offset in range(1,lim): 
            print(proxima_permutacao(nova))
fim = time.time()
print("Tempo de execução: ", fim - inicio)

Eis o resultado para a sequência \( \{1,2,3,4\} \):

Algoritmo-L
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]
Tempo de execução: 0.0010013580322265625

Para a sequência \( \{0,1,2,3\} \), temos:

Algoritmo-L
[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]
Tempo de execução: 0.0010025501251220703

A implementação acima é eficaz, mas o desafio é sobre como melhorar o desempenho do Algoritmo L quando o valor de \(j\) é próximo a \(n\).

A solução foi apresentada em [J. P. N. Phillips, Comp. J. 10 (1967), 311.] Assumindo \(n \gt 3\), pode-se substituir os passos L2-L4 por:

Adaptação do Algoritmo-L (tradução nossa):
L1. [Visite.] Visite a permutação \(a_{1} a_{2} ... a_{n}\).
L2'. [Caso mais simples] Faça \( y \leftarrow a_{n-1}\) e \(z \leftarrow a_{n}\) . Se \( y \lt z\), faça \(a_{n-1} \leftarrow z\), \(a_{n} \leftarrow y\), e retorne para L1.
L2.1'. [Próximo caso mais simples] Faça \(x \leftarrow a_{n-2}\). Se \(x \geq y\), vá ao passo L2.2'. Caso contrário, faça \( ( a_{n-2}, a_{n-1}, a_{n}) \leftarrow (z,x,y) \) se \(x \lt z \), \( (y,z,x) \) se \(x \geq z \). Retorne para L1.
L2.2'. [Encontre \(j\).] Faça \( j \leftarrow n-3\) e \(y \leftarrow a_{j}\). Enquanto \(y \geq x\), faça \( j \leftarrow j-1\), \(x \leftarrow y\), e \(y \leftarrow aj\). Termine se \(j=0\).
L3'. [Aumento fácil?] Se \(y \lt z\), faça \(a_{j} \leftarrow z \), \(a_{j+1} \leftarrow y\), \(a_{n} \leftarrow x\), e vá para L4.1'.
L3.1'. [Aumente \(a_{j}\).] Faça \(l \leftarrow n-1\) ; se \( y \geq a_{l}\), repetidamente decresça \(l\) por \(1\) até que \( y \lt a_{l}\). Então faça \(a_{j} \leftarrow a_{l}\) and \(a_{l} \leftarrow y\).
L4'. [Inicie a inversão.] Faça \(a_{n} \leftarrow a_{j+1}\) e \(a_{j+1} \leftarrow z\).
L4.1'. [Inverta \(a_{j+2} \ldots a_{n-1}\).] Faça \(k \leftarrow j+2\) e \( l \leftarrow n-1\). Então, enquanto \(k \lt l\), troque \(a_{k} \leftrightarrow a_{l}\), faça \(k \leftarrow k+1\), \( l \leftarrow l-1\). Retorne para L1.

Eis a implementação em Python 3.7:

print("Permutações Lexicográficas - Exercício 1")
import time
inicio3 = time.time()

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
    y=seq[n - 1]
    z=seq[n]
    if y < z:
        seq[n-1]=z
        seq[n]=y
        return seq
    x=seq[n - 2]
    if x < y:   
        if x < z:
            seq[n - 2] = z
            seq[n - 1] = x
            seq[n] = y
        else:
            seq[n - 2] = y
            seq[n - 1] = z
            seq[n] = x
        return seq
    else:
        j= n - 3
        y= seq[j]
        while not j<0 and not y < x:
            j -= 1
            x = y
            y= seq[j]
        if j < 0:
            troca(seq,0,n)

        if y < z:
            seq[j]=z
            seq[j+1]=y
            seq[n]=x

        else:

            l=n-1
            while not l<0 and not y < seq[l]:
                l-= 1
            seq[j]=seq[l]
            seq[l]=y
            seq[n]=seq[j+1]
            seq[j+1]=z
            k=j+2
            l=n-1
            while not l<0 and k < l:
                k += 1
                l -= 1

        inverte(seq,j+2,n-1)
    return seq

if __name__ == '__main__':
    import math
    nova3=[0,1,2,3]
    tam=len(nova3)
    lim=math.factorial(tam)
    print(nova3)
    if tam>1:
        for offset in range(1,lim): 
            print(proxima_perm(nova3))

fim3 = time.time()
print("Tempo de execução: ",fim3 - inicio3) 

Para a sequência \( \{0,1,2,3\}\), são \(n! = 4! = 24\) permutações, pois não há 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:

Permutações Lexicográficas - Exercício 1
[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]
Tempo de execução: 0.0009756088256835938

Para a sequência \( \{0,1,2,3\}\), o tempo de execução do algoritmo L (Pandita) foi de 0.0010025501251220703 segundos e o tempo de execução do algoritmo L adaptado (Phillips) foi de 0.0009756088256835938 segundos, demonstrando maior eficiência da solução apresentada em [J. P. N. Phillips, Comp. J. 10 (1967), 311.]

comentou Jul 3 por Carlos A T Haraguchi (21 pontos)  
Cláudia, eu achei bom seu post trazer a tradução das referências, o que nos economiza esforço em buscá-las e traduzi-las. Ainda mais com essa notação dos índices que confunde um pouco.

Quanto ao código que você implementou tenho duas observações.

1 - Acho que no código de "Permutações Lexicográficas", mais perto do final, a linha
 "tam=len(nova)" deveria ser "tam=len(nova3)", não?
2 - Vi que você faz a comparação "n<1" dentro das funções "proxima_permutacao" e "proxima_perm". Pelo que entendi, é para evitar que sequências de apenas 1 elemento sejam manipuladas pelas funções. Mas, essas funções são chamadas n! vezes. Acredito que você pode reduzir o número de comparações de n! para 1 se transferir essa verificação para uma linha antes do loop (veja observação 4).
3 - A mesma repetição ocorre dentro dos loops "for offset in range(0,lim)" ao final dos códigos. Você verifica a cada iteração se se trata da primeira sequência. Além disso, usa uma variável auxiliar "lista".
4 - Como sugestão, em ambas as funções "proxima_permutacao" e "proxima_perm", eu eliminaria as linhas
---
if n < 1:
    return
---
e substituiria o trecho
---
for offset in range(0,lim):
    if offset==0:
        lista=nova
    else:
        lista=nova
        nova=proxima_permutacao(lista)
    print(nova)
---
por
---
print(nova)
if tam > 1:
    for offset in range(1,lim): print(proxima_permutacao(nova))
---
e o trecho
---
for offset in range(0,lim):
    if offset==0:
        lista=nova3
    else:
        lista=nova3
        nova3=proxima_perm(lista)
    print(nova3)
---
por
---
print(nova3)
if tam > 1:
    for offset in range(1,lim): print(proxima_perm(nova3))
---
Assim reduziria, em cada código, 2(n!) comparações para 1 apenas.
comentou Jul 3 por claudiaeirado (51 pontos)  
editado Jul 3 por claudiaeirado
Carlos, muito obrigada pelas observações. Acredito que são todas pertinentes.
Respostas:
1- Realmente houve um erro de digitação.
2 , 3, 4: Eu não havia me atentado a essa questão, com a retirada da comparação do tamanho da sequência de dentro do looping para fora, ficará mais eficiente.
Implementei as mudanças sugeridas.
comentou Jul 3 por claudiaeirado (51 pontos)  
editado Jul 3 por claudiaeirado

Segue o algoritmo-L:

print("Algoritmo-L")
#Faz a troca da posição
def troca(seq, j, l):
    seq[j], seq[l] = seq[l], seq[j]

#Inverte a sequencia em L4
def inverte(seq, j, l):
    for offset in range((l - j + 1) // 2):
        troca(seq, j + offset, l - offset)


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, 3, 4]
    tam=len(nova)
    lim=math.factorial(tam)
    print(nova)
    if tam>1:
        for offset in range(1,lim): 
            print(proxima_permutacao(nova))

Para o Algoritmo-L adaptado, apresentada em [J. P. N. Phillips, Comp. J. 10 (1967), 311.], temos:

print("Permutações Lexicográficas - Exercício 1")
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
    y=seq[n - 1]
    z=seq[n]
    if y < z:
        seq[n-1]=z
        seq[n]=y
        return seq
    x=seq[n - 2]
    if x < y:   
        if x < z:
            seq[n - 2] = z
            seq[n - 1] = x
            seq[n] = y
        else:
            seq[n - 2] = y
            seq[n - 1] = z
            seq[n] = x
        return seq
    else:
        j= n - 3
        y= seq[j]
        while not j<0 and not y < x:
            j -= 1
            x = y
            y= seq[j]
        if j < 0:
            troca(seq,0,n)

        if y < z:
            seq[j]=z
            seq[j+1]=y
            seq[n]=x

        else:

            l=n-1
            while not l<0 and not y < seq[l]:
                l-= 1
            seq[j]=seq[l]
            seq[l]=y
            seq[n]=seq[j+1]
            seq[j+1]=z
            k=j+2
            l=n-1
            while not l<0 and k < l:
                k += 1
                l -= 1

        inverte(seq,j+2,n-1)
    return seq

if __name__ == '__main__':
    import math
    nova3=[0,1,2,3]
    tam=len(nova3)
    lim=math.factorial(tam)
    print(nova3)
    if tam>1:
        for offset in range(1,lim): 
            print(proxima_perm(nova3))
comentou Jul 4 por Carlos A T Haraguchi (21 pontos)  
Cláudia, fico feliz que tenha ajudado.

Vi que você acrescentou um cronômetro. Achei uma boa ideia!
comentou Jul 4 por claudiaeirado (51 pontos)  
Sim, percebi que seria importante possuir um comparativo do tempo de execução, pois o exercício era sobre mostrar como o algoritmo adaptado é mais rápido que o original.
...