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.