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
98 visitas
perguntada Jun 30, 2019 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, 2019 por claudiaeirado (51 pontos)  
editado Jul 3, 2019 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, 2019 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, 2019 por claudiaeirado (51 pontos)  
editado Jul 3, 2019 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, 2019 por claudiaeirado (51 pontos)  
editado Jul 3, 2019 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, 2019 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, 2019 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.
...