Compute a média e a variância do número de comparações realizadas pelo Algorítmo L em (a) passo L2 e (b) passo L3, quando os elementos {a1, ..., an} são distintos.

Question

Trata-se do Exercício 5, constante na página 345 do livro The Art of Computer Programming, Volume 4A: Combinatorial Algorithms – Donald E. Knuth.

Answer 1

Segue abaixo descrição do Algoritmo L, copiado do link http://prorum.com/?qa=4302/explique-algoritmo-rapido-racionalizando-operacoes-proximo&show=4302#q4302

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 a1,a2,…,an, inicialmente ordenada
tal que a1≤a2≤…≤an, este algoritmo gera todas as permutações de
{a1,a2,…,an}, 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 a0 é assumido para estar presente para conveniência; a0 deve ser
estritamente menor que o maior elemento an.

L1. [Visite.] Visite a permutação a1a2...an.
L2. [Ache j.] Faça j←n−1. Se aj≥aj+1, diminua j por 1 repetidamente até que aj<aj+1.
Termine o algoritmo se j=0.
L3. [Aumente aj.] Faça l←n. Se aj≥al, diminua l por 1 repetidamente até que aj<al. Então
troque aj↔al.
L4. [Inverta aj+1...an.] Faça k←j+1 e l←n. Então, se k<l, troque
ak↔al, faça k←k+1, l←l−1. Retorne para L1. )

Para encontrar a média e a variância nos passos L2 e L3 utilizou-se o mesmo programa demonstrado também no link mencionado mais acima, com algumas adaptações.

Na função proxima_permutacao(seq), nos passos L2 e L3, incluíram-se contadores a fim de identificar quantos loops foram necessários para ordenar uma nova sequência permutada (countj e countl). Cada contagem foi inserida em uma lista para cálculo da média e da variância ao fim do programa.

import matplotlib.pyplot as plt
import statistics
import math

#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
    countj = 0
    countl = 0
#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]:
        countj +=1 #conta quantas vezes há comparação em L2
        j -= 1

    if countj!=0:
        countjList.append(countj) #insere na lista apenas se tiver entrado no loop referente a L2

    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
            countl +=1 #conta quantas vezes há comparação em L3

        troca(seq, j, l)

        if countl!=0:
            countlList.append(countl) #insere na lista apenas se tiver entrado no loop referente a L3

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

Como não houve pretensão de demonstrar todas as permutações de uma sequência em ordem lexicográfica, alterou-se o passo L1 do programa original para que fossem formadas listas de 4 a 10 elementos distintos para identificar a média e variância dessas listas e suas variações por elemento adicionado.

if __name__ == '__main__': 

    dicj2 = {}
    dicl2 = {}
    mediasj = []
    mediasl = []
    varj = []
    varl = []

#Alteração no procedimento L1, dada o objetivo dessa solução  
    for i in range(4,11): 
        countjList = []
        countlList = []
        dicj = {}
        dicl = {}

        nova=list(range(i)) 
        tam=len(nova)
        lim=math.factorial(tam)

        if tam>1:
            for offset in range(1,lim): 
                (proxima_permutacao(nova))

        meanj = round(statistics.mean(countjList), 4)
        variancej = round(statistics.variance(countjList), 4)
        meanl = round(statistics.mean(countlList), 4)
        variancel = round(statistics.variance(countlList), 4)        


        dicj['media'] = meanj
        dicj['var'] = variancej
        dicl['media'] = meanl
        dicl['var'] = variancel
        dicj2[f'n={tam}'] = dicj
        dicl2[f'n={tam}'] = dicl

        mediasj.append(meanj)
        mediasl.append(meanl)
        varj.append(variancej)
        varl.append(variancel)

    print('Step L2:', dicj2, '\nStep L3:', dicl2)

Dessa maneira, o output transformou-se em um dicionário para identificação da quantidade de elementos da sequência e as respectivas média e variância.

Step L2: {'n=4': {'media': 1.2727, 'var': 0.2182},
'n=5': {'media': 1.3898, 'var': 0.3799},
'n=6': {'media': 1.4262, 'var': 0.4631},
'n=7': {'media': 1.4347, 'var': 0.4913},
'n=8': {'media': 1.4363, 'var': 0.4982},
'n=9': {'media': 1.4365, 'var': 0.4995},
'n=10': {'media': 1.4366, 'var': 0.4997}}

Step L3: {'n=4': {'media': 1.1667, 'var': 0.1667},
'n=5': {'media': 1.2424, 'var': 0.2519},
'n=6': {'media': 1.2673, 'var': 0.2963},
'n=7': {'media': 1.2734, 'var': 0.3116},
'n=8': {'media': 1.2746, 'var': 0.3154},
'n=9': {'media': 1.2748, 'var': 0.3162},
'n=10': {'media': 1.2748, 'var': 0.3163}}

Por meio de um simples gráfico, verifica-se que a partir de uma sequência de 7 elementos, a média e variância da quantidade de comparações praticamente se estabiliza.

plt.plot([4,5,6,7,8,9,10], mediasj)
plt.plot([4,5,6,7,8,9,10], mediasl)

plt.plot([4,5,6,7,8,9,10], varj)
plt.plot([4,5,6,7,8,9,10], varl)

O programa apresentou-se bastante custoso, até pelo uso da função proxima_permutacao(seq), que tem como objetivo retornar todas as permutações de cada sequência, no caso de sequências de 4 a 10 elementos.

Answer 2

Oi Camila,

Gostei da sua resposta pois tanto a explicacao quanto o codigo estao didaticos e, principalmente, pelo graficos (uma legenda seria bem-vinda, mas isso e' perfumaria). Como codigo esta' um pouco lento, deixo uma contribuicao a indicacao de um codigo mais rapido do que o codigo base usado por voce.

Note que o tempo de execucao do alternativo e' da ordem de \(9.9 \times 10^{-4}\) ao passo que tempo do codigo origional e' \(4 \times 10^{-2}\)

Link para codigo mais rapido.

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

def nextpermutationhelper(perm):
if not perm:
return perm

n = len(perm)

"""
Find k such that p[k] < p[k + l] and entries after index k appear in
decreasing order.
"""
for i in range(n - 1, -1, -1):
    if not perm[i - 1] >= perm[i]:
        break

# k refers to the inversion point
k = i - 1

# Permutation is already the max it can be
if k == -1:
    return []

"""
Find the smallest p[l] such that p[l] > p[k]
(such an l must exist since p[k] < p[k + 1].
Swap p[l] and p[k]
"""
for i in range(n - 1, k, -1):
    if not perm[k] >= perm[i]:
        perm[i], perm[k] = perm[k], perm[i]
        break

# Reverse the sequence after position k.
perm[k + 1 :] = reversed(perm[k + 1 :])

return perm


def multiset_permutation(B):
"""
We sort array first and `next_permutation()` will ensure we generate
permutations in lexicographic order
"""
A = sorted(B)
result = list()


while True:
    result.append(A.copy())
    A = next_permutation_helper(A)
    if not A:
        break


return result

if __name__ == "__main__":

    B = [1,2,3,4]

    print(multiset_permutation(B))
    fim = time.time()
    print("Tempo de execução: ", fim - inicio)



print("Algoritmo-L original")
import time
inicio = 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_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))
fim = time.time()
print("Tempo de execução: ", fim - inicio)